One shortest route is efficient. Two carefully chosen routes can make a network resilient.
Suurballe’s algorithm teaches a subtle but powerful idea: the best pair of edge-disjoint routes is not found by greedily taking the shortest path and then merely banning its edges. Instead, the first shortest path is used to reshape the problem so a second shortest-path computation can repair earlier choices when necessary.
Quick Read
- Problem: find two edge-disjoint paths from source s to target t with minimum total cost.
- Foundation: Dijkstra, shortest-path distances, reduced costs and residual graphs.
- Core move: reweight edges using shortest-path potentials so reduced costs stay nonnegative, reverse the first path in the residual structure, then run Dijkstra again.
- Cancellation: reversed edges chosen by the second path cancel corresponding first-path choices.
- Professional lesson: distinguish edge-disjoint from vertex-disjoint routing, preserve assumptions on weights, and verify both disjointness and total cost.
1. Begin with the real problem
Imagine a school campus, data centre or transport network where one connection failure should not isolate a destination. You want two routes from s to t that share no edges. Among all such pairs, you want the minimum total cost.
This is not the same as finding the two individually shortest paths. Two very short paths may share a crucial edge. It is also not always safe to take the shortest path first, delete it, and find another. The globally best pair may require changing part of the first choice.
2. Prerequisite: Dijkstra must be solid
Before Suurballe, be able to trace Dijkstra by hand. For every vertex v, keep a distance d(v) from s and a predecessor. Understand why nonnegative edge lengths allow the smallest tentative distance to become final.
The first Dijkstra run gives more than one path. It gives a shortest-path distance label for every reachable vertex. Those labels become potentials used to reweight the graph.
3. Reweighting is the conceptual hinge
For an edge u→v with original cost w(u,v), define a reduced cost:
w'(u,v) = w(u,v) + d(u) - d(v)Because d(v) ≤ d(u)+w(u,v), every reduced cost is nonnegative. Edges on a shortest-path tree can have reduced cost zero.
Why bother? Reweighting preserves relative path optimality while making the residual problem compatible with another Dijkstra run. This is the same broad potential-function idea that appears in Johnson’s all-pairs shortest-path algorithm and minimum-cost flow methods.
4. Build the residual structure
Let P1 be the first shortest path from s to t. In the residual graph, reverse each edge of P1. Intuitively, a reversed edge means the second computation may decide to undo part of P1.
That is the key reason simple deletion is too crude. Deletion says, “the first path is final.” Residual reversal says, “the first path is provisional; the second path may reroute the pair while preserving the objective.”
5. Run Dijkstra a second time
Run Dijkstra from s to t in the reduced-cost residual graph. Let the resulting path be P2′. It may use reversed edges from P1. Those reversed edges are not literal backward travel in the final answer; they encode cancellation.
6. Cancel opposing edges and decompose
Combine P1 with P2′. Whenever an original P1 edge and its reversed residual counterpart both appear, cancel them. The remaining directed edges can be decomposed into two edge-disjoint s→t paths, possibly after removing zero-cost cycles.
This is the moment learners should draw the graph. Use one colour for P1, another for P2′, and cross out opposing edge pairs. The final two paths become much easier to understand visually than from symbols alone.
7. Why the method is correct
The professional proof view is that Suurballe can be understood as a specialised minimum-cost flow procedure sending two units of flow from s to t. Reduced costs and potentials preserve optimality; residual edges encode the ability to undo prior flow; the second shortest augmenting path improves the joint solution rather than freezing the first route.
This is a recurring algorithm pattern: solve once, construct a residual problem that represents reversible choices, then solve again under transformed costs.
8. Edge-disjoint is not vertex-disjoint
Two edge-disjoint paths may still pass through the same intermediate vertex. If the requirement is that internal vertices must also be distinct, the model must change.
A standard transformation splits each vertex v into v_in and v_out connected by a capacity-one internal edge. Routing then proceeds through the split graph. Do not silently claim vertex resilience when you have only proved edge resilience.
9. A learner-friendly pseudocode skeleton
suurballe(G, s, t):
d, parent = dijkstra(G, s)
P1 = reconstruct(parent, t)
for each edge (u,v):
reduced[u,v] = w[u,v] + d[u] - d[v]
R = residual_graph(G, P1, reduced)
d2, parent2 = dijkstra(R, s)
P2prime = reconstruct(parent2, t)
H = combine_and_cancel(P1, P2prime)
return decompose_into_two_s_t_paths(H)The code hides important engineering decisions: parallel edges, unreachable nodes, predecessor storage, path reconstruction, zero-cost cycles and stable edge identifiers. Professional implementations should make those explicit.
10. Complexity
The basic two-path form performs two Dijkstra-style shortest-path computations plus linear residual bookkeeping. With suitable priority queues, the dominant cost is therefore close to two shortest-path runs on the same graph. Exact bounds depend on the graph representation and priority queue.
The important professional habit is to state the resource and assumptions: number of vertices, number of edges, edge-weight restrictions, priority-queue model, and whether explicit path reconstruction is included.
11. Common mistakes
- Deleting the first shortest path instead of allowing residual cancellation.
- Using negative original edge weights with ordinary Dijkstra without changing the method.
- Confusing two shortest paths with a minimum-total-cost disjoint pair.
- Calling edge-disjoint routes vertex-disjoint.
- Forgetting that reversed residual edges represent cancellation, not final traversal.
- Losing edge identity in a multigraph.
- Returning two routes without verifying they really are disjoint.
12. Verification tests
- A graph with exactly two obvious disjoint routes.
- A graph where naive “shortest path then delete” is suboptimal.
- A graph with no pair of edge-disjoint s→t paths.
- Parallel edges with different weights.
- Zero-weight edges.
- A case where the second residual path uses a reversed edge and forces cancellation.
For every successful result, assert: both paths start at s, end at t, are valid in the original graph, share no edges, and have a total cost matching an independent min-cost-flow answer on small random graphs.
13. Learn it with Predict → Run → Investigate → Modify → Make
- Predict: guess whether greedy deletion will find the best pair on a six-node graph.
- Run: trace the first Dijkstra and record every d(v).
- Investigate: compute every reduced cost and explain why none is negative.
- Modify: change one edge weight and predict which residual cancellation changes.
- Make: implement the algorithm only after the trace is understood.
This progression follows programming-education evidence that learners often benefit from prediction, code reading, tracing and modification before full construction.
14. Beginner → professional pathway
- Beginner: find shortest paths and identify shared edges.
- Foundation: calculate Dijkstra distances and reduced costs.
- Intermediate: build the residual graph and perform cancellation by hand.
- Advanced: derive the min-cost-flow interpretation and prove reduced costs are nonnegative.
- Professional: distinguish edge versus vertex disjointness, test against maintained libraries, verify assumptions, and use independent optimality checks on small instances.
Learning Hall Boundary
This article owns Suurballe’s algorithm as a learning object for minimum-total-cost disjoint shortest paths, reduced-cost reweighting, residual cancellation and resilient route construction. It complements existing shortest-path, flow and graph articles. It does not replace MindOS, Bolt or Student/Studying Interface canonical jobs, and it does not expose private eduKateAI implementation details.
Sources and further reading
- J. W. Suurballe, Disjoint Paths in a Network, Networks, 1974.
- J. W. Suurballe & R. E. Tarjan, A Quick Method for Finding Shortest Pairs of Disjoint Paths, Networks, 1984.
- LEMON Graph Library, Suurballe algorithm documentation.
- JGraphT, SuurballeKDisjointShortestPaths.
- Sentance, Waite & Kallia, Teachers’ Experiences of Using PRIMM to Teach Programming in School, SIGCSE 2019.
Professional rule: you understand Suurballe when you can explain why reweighting preserves shortest-path structure, why residual reversal allows earlier choices to be repaired, and how to verify that the final pair is genuinely disjoint and minimum-cost under the stated model.
