Shortest Paths
When edges carry costs, such as kilometres, milliseconds or link weights, the path with the fewest hops is no longer the cheapest, and breadth-first search returns the wrong answer. Dijkstra's algorithm fixes that with one greedy rule: always finalize the closest node not yet finalized. The rule is correct exactly as long as no edge has a negative cost.
Routers and route planners run this algorithm, or close relatives of it, all day. What they optimize is whatever number sits on the edges, so choosing the weight is choosing the policy, and the algorithm will follow that policy to the letter.
Why Hops Are Not Enough
A route made of two 100-kilometre roads loses to a route made of four 10-kilometre roads: 200 kilometres against 40. Breadth-first search from the previous topic counts edges, reaches the far end first along the two-hop route, and returns it. Weights change the question from "fewest edges" to "smallest sum", and a search that ignores them answers the old question.
The same mismatch hides in any graph whose edges differ in cost: a network path through two slow intercontinental links against four fast local ones, a build that routes work through a slow machine because it is one step closer.
Dijkstra by Picture
Give every node a tentative distance: 0 for the start and infinity for the rest. Then repeat one step. Take the unsettled node with the smallest tentative distance and settle it, which declares its distance final. For each edge leaving it, check whether reaching the neighbour through it is cheaper than the neighbour's current tentative distance, and if so lower that distance and remember where it came from. That check is called relaxing the edge.
The figure runs it on six nodes. Step 1 settles S at 0 and gives B a tentative 2 and A a tentative 7. Step 2 settles B, the closest, and relaxing its edges lowers A from 7 to 5, because going through B costs 2 plus 3. Step 3 settles A at 5 and lowers C to 7. Step 4 settles C at 7 and lowers D to 10. Two more steps settle D at 10 and T at 11. The settled region grows outward like a ripple, in order of distance.
The answer disagrees with breadth-first search. Three routes from S to T tie at the fewest hops, and the one breadth-first search returns is S, A, C, T: three edges costing 14. Dijkstra's route is S, B, A, C, D, T: five edges costing 11.
The Priority Queue Underneath
"Take the unsettled node with the smallest tentative distance" is what a heap does, the priority queue from Chapter 6. With a heap, each settle and each lowered distance costs about log n, and the whole run costs about (nodes + edges) × log nodes. With a plain scan for the minimum instead, each settle scans every node, and the run costs about nodes squared.
For a hundred routers either is instant. For a road network of 20 million junctions, nodes squared is 400 trillion steps, days of computing, against seconds with the heap, which is why every serious implementation uses a heap. The heap's log factor is also why breadth-first search, which needs only a plain queue, remains the right tool when every edge costs the same.
Why Negative Weights Break It
Settling a node assumes that no path found later can come back cheaper. That holds when every edge adds a non-negative cost, because any later path starts from a node at least as far away and can only grow. One negative edge breaks the assumption, and Dijkstra returns a wrong distance with no error.
The figure has three nodes. S reaches A for 2 and B for 5, and an edge from B to A costs minus 4. Dijkstra settles S at 0, then A at 2, the closest. Only afterwards does it settle B at 5 and see that S to B to A costs 5 minus 4, which is 1. A is already final, so the answer stays at 2. Run in Python on this graph, a textbook Dijkstra reports 2 and the true shortest distance is 1.
Bellman–Ford handles negative edges by relaxing every edge in the graph, nodes minus 1 times over, which costs nodes times edges. If one more round still lowers a distance, the graph contains a negative cycle, a loop whose total cost is below zero, and "shortest" does not exist at all: going round once more always costs less. A currency-exchange loop that ends with more money than it started with has this shape, and Bellman–Ford is how such loops are detected.
The Same Algorithm in Routers and Maps
Link-state routing protocols, OSPF and IS-IS, have every router hold a map of all the links in its area and run Dijkstra over it to build its forwarding table; the protocols themselves belong to Networking Deep Dive. A maps application cannot afford plain Dijkstra across a continent, because plain Dijkstra settles every node closer than the destination. It steers the search toward the goal with a distance estimate, an algorithm called A-star, and precomputes shortcuts across the road network ahead of time, so a cross-country query touches a tiny part of the graph.
What a Shortest Path Costs
One query pays for the part of the graph closer than the target, which can be most of it. A router recomputes its whole tree whenever a link changes, so a link that flaps up and down many times a minute costs CPU on every router in the area, and routing protocols spend much of their design damping it.
The weight is the policy. Minimize kilometres and the route takes the short road through the town centre. Minimize expected minutes and the answer depends on traffic, which changes the weights through the day and invalidates yesterday's tree. Minimize money and the route avoids tolls. The algorithm is identical in all three cases, and so is its confidence.
- "Dijkstra computes one path from A to B." It computes the cheapest path from the start to every node it settles, a whole shortest-path tree. Stopping at the target is an optimization, and a router keeps the whole tree.
- "Negative weights can be fixed by adding a constant to every edge." Adding k to each edge adds k per hop, which penalizes paths with more edges and changes which path is cheapest. Adding 5 to every edge in the three-node example makes the direct route to A cost 7 and the route through B cost 11, so the shifted graph now prefers a path that was not the cheapest before.
- "A-star is always faster than Dijkstra." Only with a good estimate. With an estimate of zero it is Dijkstra, and an estimate that overshoots the true remaining distance can return quickly with a path that is not the shortest.
- "The shortest path is the one with the fewest hops." Only when every edge costs the same, and in that case breadth-first search is both correct and cheaper.
- "Shortest paths, once computed, stay valid." Weights change with traffic, failed links and new links, and each change can invalidate part of the tree. Routing protocols spend most of their design on reacting to change.
- Use breadth-first search when every edge costs the same, and Dijkstra only when weights differ. The heap costs a log factor that BFS never pays.
- Check for negative weights before choosing Dijkstra. One negative edge returns wrong distances silently, not an error.
- Choose the weight as a deliberate policy: distance, time, money or latency. The algorithm optimizes exactly what it is given.
- Stop the search once the target is settled when only one path is needed. Every node settled after it is paid for nothing.
Knowledge Check
From X to Y there is a direct link of weight 10 and a three-hop route whose links weigh 2, 3 and 2. What do BFS and Dijkstra return?
- Both return the direct link, which has a single hop and is the obvious path
- BFS returns the direct link; Dijkstra returns the three-hop route of weight 7
- BFS returns the three-hop route; Dijkstra returns the direct link of weight 10
- Both return the three-hop route, since its total weight is lower than 10
Why does a single negative edge break Dijkstra's algorithm?
- The heap cannot order negative distances correctly
- A later path can undercut a node already declared final
- The algorithm loops forever around the negative edge
- It raises an error the moment it relaxes that edge
A team adds 10 to every edge weight to remove a few negative edges, then runs Dijkstra. What is the effect?
- The same paths win, each total shifted up by exactly 10
- Paths with more hops gain an advantage over short ones
- Paths with more hops are penalized, so the answer can change
- Nothing changes, since Dijkstra ignores constant offsets
A route planner uses A-star with a distance estimate that sometimes exceeds the true remaining distance. What is the risk?
- It can return quickly with a path that is not the shortest one
- It becomes slower than plain Dijkstra on every single query
- It may never terminate on a road network with any loops in it
- It changes the edge weights, so all stored distances go stale
One link in an area of 200 routers goes down and up every few seconds. What does that cost the network?
- Only the two routers at the ends of the link do any extra work
- Nothing until a nightly job recomputes the routing tables
- Every router in the area reruns its shortest-path computation
- Nothing, since the shortest paths avoid the unstable link anyway
You got correct