Checkpoint 1
Which node is settled next?
The start node has already been settled. These are the current tentative distances:
Choose before revealing the idea.
Search algorithms
Dijkstra's algorithm: shortest paths with weighted edges.
The visualiser takes most of the page so you can focus on the network. Step through the algorithm, watch tentative distances update, and see why the nearest unsettled node becomes fixed.
Think first
Dijkstra is not magic. It repeats two small decisions.
1. Choose the unsettled node with the smallest tentative distance.
2. Check its edges. If a route through this node is shorter, update the distance.
Once a node is settled, its distance is final because all edge weights are non-negative.
Checkpoint 2
Should the distance update?
Current node has distance 5. An edge of weight 3 leads to a node whose current tentative distance is 9.
5 + 3 = 8, compared with 9
Decide whether the new route improves the old distance.
Weighted graph
Start A to target G
Complexity and scale
Dijkstra is powerful, but large networks can become expensive.
The algorithm is not just drawing a path. It repeatedly chooses the next unsettled vertex and checks edges. As the number of vertices and edges grows, the amount of bookkeeping grows too.
This is where algorithmic thinking matters: the same mathematical idea can feel quick on a classroom graph and painfully expensive on a road network, game map or web-scale graph.
Edges
569
Simple scan
6.4k
Priority queue
4.1k
Rough operation growth
This simplified graph compares two common implementation models as the graph grows.
O(V²)O((V+E)log V)
Notice that this is not exponential growth. It can still become huge. For comparison, an exponential pattern like 2ⁿ would explode so quickly that by 80 vertices it is around 1.1bn even after capping the calculation for the display.
Benefits of Dijkstra
It is reliable when all edge weights are non-negative. It gives the shortest distance from one start node to every reachable node, not just one target, and the logic is beautifully inspectable.
Drawbacks
It explores outward without knowing where the target is. On large networks this can waste effort, especially if you only care about one destination. It also cannot handle negative edge weights.
Why not always use it?
In many real pathfinding problems, we use a goal-directed method instead. A* adds a heuristic: an estimate of the remaining distance to the target.
Investigate A*How could it be improved?
Use a priority queue so the smallest tentative distance is found more efficiently.
Stop early when the target has been settled if you only need one route.
Use A* when you have a useful estimate of distance to the goal.
Use specialised routing methods on huge road networks where preprocessing is worthwhile.