The problem
In a weighted graph (Unit 1), every edge has a number: a distance, a travel time, a price. The length of a route is the sum of the weights of its edges. The shortest-path problem asks: what is the route of smallest total length from a start vertex s to a target t?
In Unit 4, breadth-first search found shortest paths by counting edges. With weights that no longer works, because a route with more edges can be shorter:
We could list every route and add up its length, but the number of routes grows explosively with the size of the graph. We need something smarter.
The key idea: relaxing an edge
All the algorithms in this unit keep a best-known distance for every vertex, written d(v). It starts at 0 for the start vertex and ∞ ("no route known yet") for everything else. Then they repeatedly do one small operation called relaxing an edge:
Relaxing the edge u → v with weight w
If d(u) + w < d(v), then going to v through u beats the best route known so far. Set d(v) = d(u) + w, and remember that v's best route arrives from u.
In everyday terms: "I know a way to get to u in 10 minutes, and the road from u to v takes 5. My best way to v so far takes 20. So going via u is better: update v to 15." The algorithms differ only in which order they relax edges.
Dijkstra's algorithm
Edsger Dijkstra's method (designed in 1956, published in 1959) works when all weights are zero or positive, like distances and travel times. It grows a set of settled vertices whose distances are final, always settling the closest unsettled vertex next.
- Set d(s) = 0 and every other d(v) = ∞.
- Pick the unsettled vertex with the smallest d. Settle it: its distance is now final.
- Relax every edge leaving it.
- Repeat from step 2 until the target is settled (or every vertex is).
Watch it find the shortest route from S to T. The pink numbers are the best-known distances; amber vertices have a tentative distance; teal vertices are settled.
Swipe or scroll sideways to step through.
Start
S has distance 0. Every other place is marked ∞ (not reached yet).
Settle S (0)
S is the closest unsettled place, so settle it. Update its neighbours: A = 0 + 4 = 4, B = 0 + 2 = 2.
Settle B (2)
B (2) is now the closest. Through B: A = 2 + 1 = 3, better than 4, so update it. C = 2 + 8 = 10, D = 2 + 10 = 12.
Settle A (3)
A (3) is closest. Through A: C = 3 + 5 = 8, better than 10. Update.
Settle C (8)
C (8) is closest. Through C: D = 8 + 3 = 11, better than 12. T = 8 + 6 = 14.
Settle D (11)
D (11) is closest. Through D: T = 11 + 2 = 13, better than 14.
Settle T (13): done
T is settled at 13. Follow the arrows back: T ← D ← C ← A ← B ← S. The shortest route is S → B → A → C → D → T.
being settledtentative distancesettled (final)best way in so far
The winning route, S → B → A → C → D → T with length 2 + 1 + 5 + 3 + 2 = 13, is not at all obvious from the picture. It zigzags, and it avoids the tempting direct edges S–A (4) and B–D (10). Notice how several distances improved along the way: A went from 4 to 3, C from 10 to 8, D from 12 to 11 and T from 14 to 13. A tentative distance can keep improving, but once a vertex is settled it never changes again.
| Settled | S | A | B | C | D | T |
|---|---|---|---|---|---|---|
| (start) | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| S | 0 | 4 | 2 | ∞ | ∞ | ∞ |
| B | 0 | 3 | 2 | 10 | 12 | ∞ |
| A | 0 | 3 | 2 | 8 | 12 | ∞ |
| C | 0 | 3 | 2 | 8 | 11 | 14 |
| D | 0 | 3 | 2 | 8 | 11 | 13 |
| T | 0 | 3 | 2 | 8 | 11 | 13 |
finaljust improved
Try it. Using the final picture, what is the shortest distance from S to D, and what route achieves it? Is there a second route of the same length?
Show answer
d(D) = 11, via S → B → A → C → D (2 + 1 + 5 + 3). The other candidates are S → B → D (2 + 10 = 12) and S → A → C → D (4 + 5 + 3 = 12), so the 11-route is the only shortest one.
Why Dijkstra works
The crucial claim is: when the closest unsettled vertex is settled, its distance really is final. Here's the intuition.
Suppose vertex x is the closest unsettled vertex, with d(x) = 8. Could there be a sneaky shorter route to x? Any route from S to x has to leave the settled region at some point and enter an unsettled vertex y. Reaching y costs at least d(y), and d(y) ≥ 8 because x was the closest. After that, the rest of the route only adds more, since weights are never negative. So no route to x can cost less than 8.
Dijkstra's algorithm therefore settles vertices in order of their true distance from the start, like a wave spreading out at constant speed. It's breadth-first search's big sibling: BFS spreads in steps of one edge, Dijkstra spreads in steps of actual distance.
Worth knowing
On a graph with n vertices and m edges, a well-implemented Dijkstra's algorithm takes time roughly proportional to m + n log n. That's fast enough for continental road networks, especially combined with the extra tricks in the last section.
Negative weights
Can an edge weight be negative? On a road map, no. But weights don't have to be distances:
- A delivery driver might be paid on some legs (negative cost) and pay tolls on others.
- An electric car going downhill can gain battery charge.
- In finance, a series of currency exchanges can be turned into a graph where some weights are negative.
Negative weights break the argument above, and Dijkstra can give wrong answers:
A negative edge
A negative cycle
On the left, Dijkstra settles A too early. Once A is settled it's never revisited, so the cheaper route through B is missed.
The right-hand picture is worse. A cycle whose total weight is negative is called a negative cycle. If a route can reach one, it can go round it again and again, getting "shorter" every time without limit. Then shortest paths don't exist at all. In currency trading, a negative cycle corresponds to an arbitrage opportunity: a loop of exchanges that ends with more money than it started with.
Bellman–Ford
The Bellman–Ford algorithm (Lester Ford, 1956; Richard Bellman, 1958) handles negative weights by being patient instead of greedy. It doesn't settle anything early. It just relaxes every edge, over and over:
- Set d(s) = 0 and everything else to ∞.
- Repeat n − 1 times: relax every edge in the graph.
- Do one more round. If any distance still improves, there is a negative cycle.
Why n − 1 rounds? A shortest path never needs to repeat a vertex (without negative cycles, a loop can only make it longer or keep it the same), so it has at most n − 1 edges. After round 1, every shortest path with 1 edge has been found; after round 2, every one with up to 2 edges; and so on.
Here's Bellman–Ford on the left-hand graph above, relaxing the edges in the order S → A, S → B, B → A:
| Round | d(S) | d(A) | d(B) | What happened |
|---|---|---|---|---|
| start | 0 | ∞ | ∞ | |
| 1 | 0 | 1 | 3 | S → A sets A = 2; S → B sets B = 3; B → A improves A to 3 − 2 = 1 |
| 2 | 0 | 1 | 3 | Nothing changes: done (and no negative cycle) |
It gets the right answer, d(A) = 1, where Dijkstra didn't. The price is speed: Bellman–Ford takes time proportional to n × m, much slower than Dijkstra on big graphs. So the rule of thumb is: non-negative weights, use Dijkstra; negative weights possible, use Bellman–Ford.
Try it. Run one extra round of Bellman–Ford on the negative cycle A → B → C → A (weights 2, −4, 1), starting from A. What tells you something is wrong?
Show answer
Start: A = 0, B = ∞, C = ∞. Round 1 (edges A → B, B → C, C → A): B = 2, C = −2, then A = −2 + 1 = −1. A started at 0 and has dropped to −1. Round 2 (the n − 1 = 2nd round) lowers everything again: B = 1, C = −3, A = −2. The extra round lowers them again, and they would keep falling forever. Because a distance still improves after n − 1 rounds, there must be a negative cycle.
All pairs at once: Floyd–Warshall
Sometimes you want the distance between every pair of places, like the mileage chart in a road atlas. The Floyd–Warshall algorithm (1962) builds that whole table with three nested loops and a lovely idea: allow intermediate stops one at a time.
Start with a table of direct roads only (∞ where there's no direct road). Then:
- Allow routes to pass through town 1. For every pair (a, b), check whether going a → 1 → b beats the table entry.
- Now also allow town 2 as a stop. Check every pair again.
- Then town 3, then town 4.
Before: direct roads only
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 3 | 8 | 7 |
| 2 | 3 | 0 | 2 | ∞ |
| 3 | 8 | 2 | 0 | 1 |
| 4 | 7 | ∞ | 1 | 0 |
After: true shortest distances
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 3 | 5 | 6 |
| 2 | 3 | 0 | 2 | 3 |
| 3 | 5 | 2 | 0 | 1 |
| 4 | 6 | 3 | 1 | 0 |
Here's how each change happened:
- Via town 1: 2 → 1 → 4 costs 3 + 7 = 10, beating ∞. (Temporary: it improves again later.)
- Via town 2: 1 → 2 → 3 costs 3 + 2 = 5, beating the direct road of 8.
- Via town 3: 1 → 3 → 4 costs 5 + 1 = 6, beating 7. And 2 → 3 → 4 costs 2 + 1 = 3, beating 10.
- Via town 4: nothing improves. Done.
Floyd–Warshall takes time proportional to n3, so it suits graphs with up to a few thousand vertices. It also works with negative edges (but not negative cycles).
Shortest paths in the real world
A national road network has tens of millions of junctions. Plain Dijkstra spreads out in a circle around the start, so a trip from one end of a country to the other would explore almost the whole country. Real route planners add two big ideas:
- Head towards the goal. The A* algorithm (1968) is Dijkstra with a sense of direction. It adds a guess of the remaining distance, such as the straight-line distance to the destination, so the search spreads out mostly towards the target instead of in all directions.
- Do the work in advance. Systems precompute shortcuts, for example "from this motorway junction to that one is 84 km". Then each query only needs to explore a tiny part of the graph. This kind of preprocessing is what makes answers come back in milliseconds.
The same algorithms route internet traffic (routers constantly run shortest-path calculations to decide where to send data), plan robot movements, find the cheapest sequence of flights, and even align DNA sequences, where the "graph" is a grid of possible matches.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. In the Dijkstra example, the edge B–C (weight 8) never ends up on a shortest path from S. Why?
Show answer
Reaching C via B costs 2 + 8 = 10, but via A it costs 3 + 5 = 8. Once a cheaper way into C exists, B–C is never useful for routes starting at S.
2. You run Dijkstra on a graph where every edge has weight 1. What does it behave like?
Show answer
Breadth-first search. It settles all vertices at distance 1, then all at distance 2, and so on, exactly like BFS's layers.
3. Someone suggests fixing negative weights by adding 10 to every edge, so they're all positive, then running Dijkstra. Does this work?
Show answer
No. Adding 10 per edge punishes routes with many edges more than routes with few. In the S, A, B example, S → A becomes 12 and S → B → A becomes 13 + 8 = 21, so the "shortest" route changes from S → B → A to S → A. The trick changes the problem.
4. A graph has 1,000 vertices. How many rounds does Bellman–Ford need in the worst case, and how many to check for negative cycles?
Show answer
999 rounds (n − 1), plus 1 extra round to check whether anything still improves.
5. In the Floyd–Warshall example, a new road opens between towns 2 and 4 with length 2. Which entries of the final table change?
Show answer
2 ↔ 4 drops from 3 to 2. Check the others: 1 ↔ 4 via 2 would be 3 + 2 = 5, beating 6, so 1 ↔ 4 becomes 5. 3 ↔ 4 stays 1, and 1 ↔ 3 stays 5. So two entries change (each appearing twice in the symmetric table).
6. True or false: a shortest path between two vertices is always unique.
Show answer
False. In Unit 1's town map, School to Shop had two different 10-minute routes. Many graphs have ties.
Summary and glossary
- In a weighted graph, the shortest route minimises total weight, not the number of edges.
- Every algorithm here is built from relaxing edges: "is going via u better than what I know?"
- Dijkstra settles the closest unsettled vertex each time. It's fast and correct when weights are never negative.
- Negative edges can fool Dijkstra; negative cycles mean shortest paths don't exist.
- Bellman–Ford relaxes every edge n − 1 times, handles negative edges and detects negative cycles.
- Floyd–Warshall finds all pairs' distances by allowing intermediate stops one at a time.
- Shortest path
- A route with the smallest possible total weight.
- Relaxation
- Improving a vertex's best-known distance using an edge into it.
- Settled vertex
- In Dijkstra's algorithm, a vertex whose distance is final.
- Negative cycle
- A cycle whose weights add up to less than zero.
- Arbitrage
- A loop of trades that ends with a profit; a negative cycle in disguise.
- A*
- Dijkstra's algorithm guided by an estimate of the remaining distance.
- All-pairs shortest paths
- The distances between every pair of vertices.