AlgoScope

Shortest Paths

algorithmadvancedTime O((V + E) log V) Dijkstra, O(V x E) Bellman-FordSpace O(V)

With weights on the edges, the nearest vertex is no longer the one discovered first. Dijkstra keeps a tentative distance for everyone, fixes the smallest one, and relaxes its edges; that works because a non-negative edge can never make a settled vertex closer. Bellman-Ford skips the fixing and simply relaxes every edge V - 1 times, which is slower but survives negative weights and can even detect a negative cycle.

4121530✓01234

Bellman-Ford from 0. No settling: relax every edge, then do it again, 4 times at most, since a shortest path uses at most 4 edges. Negative weights are fine. If a further pass still improves something, the graph has a negative cycle and distances mean nothing.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.

  1. 0 is at 0, the edge to 1 weighs 4, 1 is at infinity. Improve?

    • Improves, update the distance
    • No better, leave it

    Answer: Improves, update the distance. 4 beats infinity, so the distance drops.

  2. 0 is at 0, the edge to 2 weighs 1, 2 is at infinity. Improve?

    • Improves, update the distance
    • No better, leave it

    Answer: Improves, update the distance. 1 beats infinity, so the distance drops.

  3. 2 is at 1, the edge to 1 weighs 2, 1 is at 4. Improve?

    • Improves, update the distance
    • No better, leave it

    Answer: Improves, update the distance. 3 beats 4, so the distance drops.

  4. 1 is at 3, the edge to 3 weighs 1, 3 is at infinity. Improve?

    • Improves, update the distance
    • No better, leave it

    Answer: Improves, update the distance. 4 beats infinity, so the distance drops.

  5. 3 is at 4, the edge to 4 weighs 3, 4 is at infinity. Improve?

    • Improves, update the distance
    • No better, leave it

    Answer: Improves, update the distance. 7 beats infinity, so the distance drops.

How it runs, step by step

  1. Bellman-Ford from 0. No settling: relax every edge, then do it again, 4 times at most, since a shortest path uses at most 4 edges. Negative weights are fine. If a further pass still improves something, the graph has a negative cycle and distances mean nothing.

    Bellman-Ford from vertex 0 over 6 edges.

  2. Pass 1, edge 0 to 1: 0 + 4 = 4 against infinity. Shorter, so 1 becomes 4.

    Pass 1: edge 0 to 1 improves 1 to 4.

  3. Pass 1, edge 0 to 2: 0 + 1 = 1 against infinity. Shorter, so 2 becomes 1.

    Pass 1: edge 0 to 2 improves 2 to 1.

  4. Pass 1, edge 2 to 1: 1 + 2 = 3 against 4. Shorter, so 1 becomes 3.

    Pass 1: edge 2 to 1 improves 1 to 3.

  5. Pass 1, edge 1 to 3: 3 + 1 = 4 against infinity. Shorter, so 3 becomes 4.

    Pass 1: edge 1 to 3 improves 3 to 4.

  6. Pass 1, edge 3 to 4: 4 + 3 = 7 against infinity. Shorter, so 4 becomes 7.

    Pass 1: edge 3 to 4 improves 4 to 7.

  7. End of pass 1: 5 improvements, and 1 edge that could not help. Some distances moved, so their neighbours may improve on the next pass.

    Pass 1 made 5 improvements.

  8. End of pass 2: 0 improvements, and 6 edges that could not help. Nothing moved, so every distance is final. Stop early.

    Pass 2 made 0 improvements.

  9. Distances from 0: 0: 0, 1: 3, 2: 1, 3: 4, 4: 7. 2 passs over 6 edges: O(V x E), slower than Dijkstra but correct with negative weights.

    Bellman-Ford finished after 2 passes.

Remember

  • Relaxing an edge u to v means: if dist[u] + w < dist[v], update dist[v]. Both algorithms are made of that.
  • Dijkstra settles the smallest tentative distance, which is only safe without negative edges.
  • Bellman-Ford relaxes all edges V - 1 times; an improvement on pass V means a negative cycle.

Topics covered

Related

Where this is used

NetworkingOSPF and IS-IS link-state routing

OSPF has every router flood a description of its own links to the whole area, so all of them end up holding the same map, and each then runs Dijkstra over that map with itself as the source. Keeping only the first hop of each shortest path turns the resulting tree into a forwarding table, and because the routers computed it from identical input they agree on where a packet goes instead of bouncing it between them. OSPF derives link cost from interface bandwidth, and neither protocol admits a negative cost, which is not a coincidence: the settle step would be unsound the moment an operator could configure one. IS-IS floods its link state in a different encoding and then runs the same computation.

NetworkingRIP and distance-vector routing

RIP is Bellman-Ford with the edge list spread across the network: each router stores a distance per destination, periodically tells its neighbours, and relaxes whatever it hears, which is one pass of the inner loop with purely local knowledge. The trouble is that a router cannot see whether a neighbour's estimate already routes through itself, so when a link dies two of them can keep relaxing each other's stale numbers upward a hop at a time, which is the count-to-infinity problem. RIP's answer is to declare 16 to be infinity, so the pointless counting stops within sixteen rounds; the protocol's famous hop limit is really a termination bound for a distributed relaxation.

MappingRoad routing engines

OSRM and GraphHopper both put Dijkstra at the centre of a route query, but a continental road graph holds tens of millions of vertices and a plain search settles a large share of them before it reaches the destination. Two fixes ship in production. Searching from both endpoints replaces one search of radius r with two of radius r/2, and the stopping rule is the subtle part: the first time the two frontiers touch you have a path, not yet the shortest one, so the search runs on until nothing left in either queue can beat it. Precomputing shortcut edges with contraction hierarchies lets a query hop over whole stretches of road in a single relaxation, which is what OSRM's contract stage and GraphHopper's speed mode build. One-way streets and turn restrictions are encoded as edges rather than handled as special cases, which is why the same algorithm covers them.

Build systemsCritical path in build systems

Bazel ends a build by printing a critical path: the chain of actions whose durations add up to the fastest wall-clock time the build could possibly take, however many cores you throw at it. An action graph is a DAG, so that number comes from this lesson's single relaxation pass in topological order with the comparison flipped to keep the maximum, and the chain itself from the parent pointers. Longest path is only tractable because the graph is acyclic - in a graph with cycles it is NP-hard - which is the practical reason build and task graphs are required to have no cycles.

Why it works this way

Why not just add a constant to every weight to remove the negatives?

It is the first fix everyone tries and it quietly changes the answer. Adding C to every edge adds C times the number of edges to a path, so a four-hop route is penalised twice as hard as a two-hop one and a different path wins. The reweighting that does work is Johnson's: run Bellman-Ford once from a virtual source joined to every vertex by a 0 edge to get a potential h(v), then replace w(u, v) with w(u, v) + h(u) - h(v). Those terms telescope along a path, so every route between the same pair shifts by the same h(s) - h(t), the ordering survives, and Dijkstra can run on the result.

Why V - 1 passes, and what an improvement on pass V really tells you

After pass k, every vertex whose shortest path uses at most k edges holds its final value: that path's last edge is relaxed during pass k at the latest, and its prefix was already correct after pass k - 1. A shortest path never repeats a vertex, so it has at most V - 1 edges and V - 1 passes finish the induction. That is exactly why a further improvement on pass V proves a negative cycle - the only way to beat every simple path is to go round something. Be careful reading the result though: the vertices that drop on that pass are the ones reachable from a negative cycle, not necessarily on it, so to name the cycle you follow parent pointers back V times and then walk the loop you land in.

The heap version pushes duplicates instead of decreasing a key

The loop above scans for the smallest unsettled distance, which is O(V) per round and genuinely the right choice on a dense graph. The O((V + E) log V) version uses a priority queue instead, but java.util.PriorityQueue has no decrease-key, so the standard trick is to push a fresh (dist, v) pair on every successful relaxation and leave the outdated one in the heap. The heap can therefore hold up to E entries rather than V, and a popped pair has to be discarded when its distance is larger than the current dist[v]. Skipping that guard does not corrupt the answers, because a relaxation from a stale larger distance can never win a comparison, but every stale pop rescans that vertex's whole adjacency list for nothing.

Why a deque is enough when the only weights are 0 and 1

At any moment the deque holds at most two distinct distances, d and d + 1, with all the d entries in front, so taking from the front returns the smallest tentative distance - which is the only thing the heap was ever doing, now at O(1). A 0 edge reaches its target at the same distance as the vertex just popped, so it belongs at the front; a 1 edge reaches d + 1 and belongs at the back, and either way the two-value invariant holds. A vertex can be pushed several times before it is popped, so the dist[u] + w < dist[v] test is what keeps the stale copies harmless. The idea generalises to weights 0..k as k + 1 buckets walked in order, which is Dial's algorithm.

Read more

Next up