Dijkstra's Shortest Path
Dijkstra finds cheapest routes from a start in a graph with nonnegative edge weights. It settles the smallest unsettled distance and relaxes outgoing edges. A route with more edges can cost less than one with fewer edges.
What a learner can do afterwards
- Run the algorithm on a small weighted graph, keeping the table of best-known distances
- Say why the nearest unsettled node can be fixed and never revised
- Give a graph where the fewest-hops route is not the cheapest route
1 · Read
Earlier, breadth-first search found routes with the fewest edges. Dijkstra minimizes total edge weight; all weights must be zero or positive. Keep best-known distances and settled marks. Initially use 0 for the start and infinity elsewhere. Each round settles the node with the smallest finite unsettled distance. A settled distance is final.
Trace Dijkstra by setting the start to 0 and all other distances to infinity, meaning no route found yet. Choose an unsettled node with the smallest finite distance and mark it settled. For each outgoing edge to an unsettled neighbour, add its weight to that distance. Keep the smaller of this sum and the neighbour's old distance. Copy the updated table row, then repeat. Stop when no finite unsettled distance remains. Either node may be chosen when minima tie.
Relaxing compares the old cost with a route through the chosen node. With P settled at 4, Q at 13, and edge P to Q of weight 5, the candidate is 4 + 5 = 9. Lower Q to 9 and record P as its predecessor. A larger candidate changes nothing. On a tie, keep the predecessor.
For nonnegative weights, suppose a cheaper route to the next chosen node existed. Take the first unsettled node on that route. Relaxing its settled predecessor has already given it a best-known distance no greater than that route's prefix cost. The chosen node's distance is no larger, and the rest of the route cannot reduce cost. This rules out a cheaper route. Settled distances stay fixed; negative edges remove this guarantee.
Fewest edges need not mean least cost. Between the same two nodes, a two-edge route costing 20 + 20 totals 40. A three-edge route costing 7 + 7 + 7 totals 21. Ordinary breadth-first search chooses by edge count, so it has no cheapest-cost guarantee for general weighted graphs. It does find cheapest routes when all edges have the same positive weight. Dijkstra handles differing nonnegative weights.
The bars compare total cost, not the number of edges.
To recover a route, keep a predecessor beside each distance. Whenever relaxation lowers a distance, replace its predecessor with the node used for that update. From a reachable target, follow predecessors back to the start, then reverse that list. For example, if R's predecessor is Q and Q's is P, the route from P to R is P, Q, R. A target still at infinity is unreachable and has no route.
With nonnegative weights, settle the smallest finite unsettled distance, relax outgoing edges, and use predecessors to recover routes.
Lesson, examples, questions and flashcards written for this dataset.
The six-node trace, settling explanation, route-cost reading and flashcards were written for this dataset.
More to read
A six-node distance trace
Use six nodes H, J, K, L, M and N. The only directed edges are H to J with weight 6, H to K with weight 1, K to J with weight 2, J to L with weight 2, K to L with weight 8, L to M with weight 1, and K to M with weight 10. N has no edges.
Start at H. In the table, inf means infinity. Each row shows distances after the named node is settled and its outgoing edges are relaxed.
| Round | H | J | K | L | M | N |
|---|---|---|---|---|---|---|
| Initial | 0 | inf | inf | inf | inf | inf |
| H | 0 | 6 | 1 | inf | inf | inf |
| K | 0 | 3 | 1 | 9 | 11 | inf |
| J | 0 | 3 | 1 | 5 | 11 | inf |
| L | 0 | 3 | 1 | 5 | 6 | inf |
| M | 0 | 3 | 1 | 5 | 6 | inf |
After H, K has the smallest finite unsettled distance, 1. Through K, J improves to 1 + 2 = 3. L becomes 9 and M becomes 11. J is selected next and lowers L to 3 + 2 = 5. L then lowers M to 5 + 1 = 6. Settling M changes nothing.
N remains at infinity, so it is unreachable from H. Stop because no finite unsettled distance remains.
The final predecessors are J: K, K: H, L: J and M: L. From M, follow M, L, J, K, H, then reverse the list. The route H, K, J, L, M costs 1 + 2 + 2 + 1 = 6.
Why a settled distance stays fixed
When a node is first discovered, its distance may still fall. Settling it is a stronger claim: no route found later will cost less. Dijkstra makes that claim only after choosing a smallest finite unsettled distance, with all edge weights nonnegative.
Suppose settled distances are already correct. Consider a rival route to the next chosen node. Its first unsettled node has a settled predecessor. That predecessor's outgoing edge has already been relaxed, so the first unsettled node has a recorded distance at most equal to the route's cost up to that point. The selected minimum is no larger. Every remaining edge adds zero or more, so this rival route cannot beat the selected distance.
A negative edge can defeat the argument. Take only three directed edges: S to A with weight 2, S to B with weight 5, and B to A with weight -4. Starting from S, the usual selection rule settles A at 2 before B. Yet S, B, A costs 5 - 4 = 1. Fixing A at 2 would miss that route. This is why Dijkstra's settled-distance guarantee requires nonnegative weights.
Choosing between hops and cost
First decide what a shortest route means in the problem. If every edge counts as one step, breadth-first search finds a route using the fewest edges. If edges carry travel costs, add those costs along each route instead.
Suppose two routes join the same start and destination. One has a single edge costing 14. The other has three edges costing 2, 3 and 4. The single-edge route uses fewer hops, but the three-edge route costs 9. A FIFO queue ordered by discovery does not compare those totals.
When all edges have the same positive weight, minimizing edge count also minimizes total cost. With different weights, ordinary BFS has no such general guarantee. It can still happen to return a cheapest route on a particular graph.
Dijkstra is one way to find cheapest routes when every edge weight is nonnegative. It compares accumulated costs before selecting the next node. It is not the only shortest-path algorithm, and its guarantee does not extend to graphs with negative edge weights.
2 · Watch
En anglaisTake it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.