Suurballe's Algorithm

Purpose: Find two vertex-disjoint paths from $s$ to $t$ whose total cost is minimum, in $O(E+V\log V)$ — two Dijkstra runs.

Algorithm

1. Run Dijkstra from $s$, obtaining distances $d(v)$ and a shortest-path tree $T$.
2. Reweight every edge with the Johnson potential:
   $w^{\prime }(u,v)=w(u,v)+d(u)-d(v)\ge 0.$
   Every edge on $T$ now has weight $0$.
3. Split vertices to enforce vertex-disjointness: replace each internal vertex $v$ with $v_{in}\to v_{out}$ of capacity 1 and cost 0. (Skip this step if you only need edge-disjoint paths.)
4. Reverse the edges of the $s\to t$ shortest path and negate their (already zero) reweighted cost, i.e. allow the second path to “undo” parts of the first.
5. Run Dijkstra again from $s$ to $t$ on the modified graph.
6. Combine the two paths: take the union of their edges, delete any pair of edges traversed in opposite directions (they cancel), and read off the two disjoint paths from what remains.

Paradigm

Successive shortest paths / min-cost flow in disguise. Suurballe’s is exactly two iterations of the SSP min-cost-flow algorithm on a unit-capacity network, with the Johnson potential keeping every Dijkstra run valid despite the negative residual edges.

Complexity

• Time: $O(E+V\log V)$ — two Dijkstra runs with a Fibonacci heap; $O(E\log V)$ with a binary heap
• Space: $O(V+E)$

Why It Works

Reweighting preserves the set of shortest paths (every $s\to t$ path changes cost by the same constant $d(t)$), and makes all weights non-negative so Dijkstra stays valid even after reversing tree edges. The reversed edges act as residual arcs: sending a second unit of flow along a reversed edge cancels the first unit there, which is precisely the “rerouting” a min-cost flow needs to reach the global optimum. Because both paths are found as augmenting paths of minimum reduced cost, the resulting flow of value 2 is a minimum-cost flow — hence the pair is jointly optimal, not merely two good paths.

Greedy fails

Taking the shortest path, deleting its edges, and taking the shortest remaining path is not optimal, and may not even find two paths when two exist. The rerouting step is essential.

Generalisation

For $k$ disjoint paths, run $k$ iterations of successive shortest paths (Suurballe-Tarjan), $O(k(E+V\log V))$. Equivalently: build a unit-capacity network and ask for a min-cost flow of value $k$.

Variants / Use Cases

• Edge-disjoint instead of vertex-disjoint — skip the vertex-splitting step
• Network reliability / protection paths — the original telecom motivation: a primary route plus a backup that survives any single node failure
• Min-cost flow — the general framework; use it directly when the disjointness or capacity constraints get more complicated
• Yen / Eppstein — solve the different problem of $k$ shortest (possibly overlapping) paths
• Menger’s theorem — the max number of disjoint $s$-$t$ paths equals the min $s$-$t$ cut, which is why flows are the right tool here