The site's ninth Shortest Paths entry, and the second (after Yen's Algorithm) to answer something other than "what's
the single cheapest path." Yen's asks for the K cheapest paths, ranked — and
those paths are free to reuse each other's edges. Suurballe's algorithm asks a narrower, stricter
question: find two paths from source to target that share no edge at all,
minimizing their combined cost. That's the question a network operator actually has when planning a
backup route — a second-best path that still crosses the one physical link most likely to fail
alongside the first isn't a backup at all, it's the same single point of failure wearing a
different name.
It's tempting to reach for Yen's algorithm here — ask for the two cheapest ranked paths and use both. That's cheaper to compute, but it doesn't promise disjointness: the second-ranked path is just the next-cheapest loopless path, and nothing stops it from sharing an edge with the first if that edge happens to sit on both routes' cheapest way through. The demo below has exactly this shape — the two cheapest paths overall share a real edge, and Suurballe's algorithm pays more to specifically avoid it.
Suurballe's algorithm gets the disjointness guarantee from a three-step trick: run Dijkstra's Algorithm once to find the first path, use its own distances to reweight every edge non-negative — the exact technique Johnson's Algorithm already uses to let Dijkstra run safely after a negative-edge pass — then reverse the first path's own edges at cost zero and run Dijkstra a second time. Whatever the second search finds, combined with what's left of the first path after any overlap cancels out, decomposes into two genuinely edge-disjoint paths. Two Dijkstra calls, not a search per candidate deviation — cheaper than Yen's despite answering a stricter question.
Five stops, eight one-way roads. Press Step or Run to watch all
five phases in order: first Dijkstra finds P1 (accent, thick); every edge gets relabeled
w→w' with its reduced cost; P1's three edges flip direction and drop to cost 0 (dashed);
a second Dijkstra runs on that modified graph and finds a path that doubles back along one of those
reversed edges; that reversal cancels the P1 edge it reverses, and everything left
combines into two final paths — path A (ink, solid) and path B
(accent, solid) — that share zero edges. Watch the dist strip below the graph track whichever search
is currently running (d1 for the first pass, d2' — reduced-cost units,
not real distance — for the second).
Two separate facts have to both be true, and the demo above lets you check each one directly.
Reweighting via P1's own distances never breaks non-negativity, for the same reason
Johnson's Algorithm relies on. The reduced weight of an edge (u, v) is
w'(u, v) = w(u, v) + d1(u) - d1(v). Dijkstra's own shortest-path property guarantees
d1(v) <= d1(u) + w(u, v) for every edge — otherwise d1(v) wasn't really
shortest — which rearranges to exactly w'(u, v) >= 0. P1's own edges are the tight
case: d1(v) = d1(u) + w(u, v) by construction, so their reduced weight lands on exactly
0. Johnson's own page proves this in
more depth; Suurballe's algorithm reuses the identical fact for a completely different purpose —
not to survive a negative edge, but to make the reversed copy of a zero-cost tree edge stay
non-negative too.
The cancellation is what turns "two searches" into "two disjoint paths," not just two
paths that happen not to collide. The second search is free to walk backward along any of
P1's reversed edges — in the demo, it does, doubling back B→A across the reversed copy
of P1's own A→B edge. That's not a bug or a coincidence: it means the second search
found it cheaper to borrow part of P1's route and give part of it back than to build an
entirely separate path from scratch. Once that reversal is walked, the corresponding forward edge
is cancelled out of the combined result — P1 contributes S→A and B→T but
not A→B anymore, and the second search's real (non-reversal) edges,
S→B and A→T, fill the gap. What's left decomposes cleanly into two paths
from S to T that touch every remaining edge exactly once, in one direction — this is the same
successive-shortest-augmenting-path idea min-cost
max-flow uses to push a second unit of flow through a residual graph; Suurballe's algorithm is
that same technique specialized to unit-capacity edges and exactly two units.
Adjacency-list version — edges is a flat list of {a, b, w} records, one
per directed edge, matching every other graph algorithm on this site:
function dijkstra(nodes, adj, source) {
const dist = new Map(nodes.map(n => [n, Infinity]));
const prevEdge = new Map(); // node -> { from, isReversal, realW }
dist.set(source, 0);
const visited = new Set();
while (true) {
let u = null, best = Infinity;
for (const n of nodes) {
if (!visited.has(n) && dist.get(n) < best) { best = dist.get(n); u = n; }
}
if (u === null) break;
visited.add(u);
for (const e of (adj.get(u) || [])) {
const nd = dist.get(u) + e.rw;
if (nd < dist.get(e.to)) {
dist.set(e.to, nd);
prevEdge.set(e.to, { from: u, isReversal: e.isReversal, realW: e.realW });
}
}
}
return { dist, prevEdge };
}
function reconstructEdges(prevEdge, source, target) {
const edges = [];
let cur = target;
while (cur !== source) {
const pe = prevEdge.get(cur);
if (pe === undefined) return null; // unreachable
edges.push({ from: pe.from, to: cur, isReversal: pe.isReversal, realW: pe.realW });
cur = pe.from;
}
return edges.reverse();
}
// edges: [{a, b, w}, ...]. Returns { path1, path2, totalCost } or null.
function suurballe(nodes, edges, source, target) {
const adj1 = new Map();
for (const { a, b, w } of edges) {
if (!adj1.has(a)) adj1.set(a, []);
adj1.get(a).push({ to: b, rw: w, isReversal: false, realW: w });
}
const { dist: d1, prevEdge: prevEdge1 } = dijkstra(nodes, adj1, source);
if (d1.get(target) === Infinity) return null; // no path exists at all
const p1Edges = reconstructEdges(prevEdge1, source, target);
const p1Keys = new Set(p1Edges.map(e => e.from + '->' + e.to));
// build the modified graph: every non-P1 edge gets its reduced weight,
// every P1 edge is replaced by its own reverse at cost 0
const adj2 = new Map();
function addEdge(a, b, rw, isReversal, realW) {
if (!adj2.has(a)) adj2.set(a, []);
adj2.get(a).push({ to: b, rw, isReversal, realW });
}
for (const { a, b, w } of edges) {
if (d1.get(a) === Infinity || p1Keys.has(a + '->' + b)) continue;
addEdge(a, b, w + d1.get(a) - d1.get(b), false, w);
}
for (const e of p1Edges) addEdge(e.to, e.from, 0, true, e.realW);
const { dist: d2, prevEdge: prevEdge2 } = dijkstra(nodes, adj2, source);
if (d2.get(target) === Infinity) return null; // no *second* disjoint path exists
const p2Edges = reconstructEdges(prevEdge2, source, target);
// cancellation: a reversal hop in P2' removes the matching P1 edge instead of being added
const kept = p1Edges.map(e => ({ ...e, active: true }));
const added = [];
for (const pe of p2Edges) {
if (pe.isReversal) {
kept.find(k => k.active && k.from === pe.to && k.to === pe.from).active = false;
} else {
added.push({ from: pe.from, to: pe.to, realW: pe.realW });
}
}
const combined = kept.filter(e => e.active).concat(added);
// decompose the combined edge set into two source-to-target paths
const outAdj = new Map();
combined.forEach((e, idx) => {
if (!outAdj.has(e.from)) outAdj.set(e.from, []);
outAdj.get(e.from).push(idx);
});
const used = new Array(combined.length).fill(false);
function extractPath() {
const path = [source];
let cur = source, cost = 0;
while (cur !== target) {
const idx = (outAdj.get(cur) || []).find(i => !used[i]);
if (idx === undefined) return null;
used[idx] = true;
cost += combined[idx].realW;
cur = combined[idx].to;
path.push(cur);
}
return { path, cost };
}
const path1 = extractPath(), path2 = extractPath();
if (!path1 || !path2) return null;
return { path1: path1.path, path2: path2.path, totalCost: path1.cost + path2.cost };
}Sometimes no second disjoint path exists, and that's a correct answer, not a bug.
Checked directly: a 4-node graph where the target has only one real incoming edge (S→A→B→T
plus a dead-end alternate S→B that never reconnects) makes the second Dijkstra's distance
to the target come back Infinity. The reference implementation above returns
null in exactly this case — a caller that assumes suurballe() always
succeeds whenever a path from source to target exists will crash or silently misread
null as "zero-cost," not "impossible."
Skipping the edge-reversal step can make a real, findable disjoint pair look impossible.
On a small graph — S→A(1)→B(1)→T(1) as P1, plus only S→B(3) and
A→T(5) as alternates, no other edges — deleting P1's edges outright (instead of reversing
them) leaves the second search with nowhere to go once it reaches B: B→T is gone, and
that's B's only remaining edge, so distance to T comes back Infinity. The real algorithm,
run on the identical graph, reverses A→B into a usable B→A hop and finds
S→A→T (cost 6) plus S→B→T (cost 4) — a genuine disjoint pair at total cost
10 that the delete-only version misses completely, not just prices worse. Checked against brute-force
enumeration to confirm 10 really is optimal, not a coincidence of this one graph.
Edge-disjoint is not vertex-disjoint. The two paths this algorithm returns are
guaranteed to share no edge, but nothing stops them from passing through the same
intermediate node by different edges. Checked directly on a small constructed graph
(S→X→A→T as P1, plus a second route S→Y→X→T that reaches T through a
completely different edge out of X): the algorithm correctly returns both paths, and they share node
X while sharing zero edges — confirmed against brute-force enumeration, not just eyeballed. A caller
that actually needs vertex-disjoint backup routes — protection against a node failing, not
just a link — needs the node-splitting extension (split every node into an in-copy and an out-copy
joined by a zero-cost edge, forcing node reuse to cost an edge) usually credited to Suurballe and
Tarjan's 1984 follow-up paper; not built on this site.
The two returned paths can differ from a brute-force search's own optimal pair while still being correct. When several disjoint pairs tie at the same minimum total cost, this algorithm's specific decomposition order picks one of them — checked directly against the stress harness below, where a brute-force check confirmed the total cost matched in every trial without requiring the exact same two paths.
Verification: the reference algorithm above was checked against brute-force
enumeration of every simple path pair on 6,000 random directed graphs (5-8 nodes, with and without
parallel edges) — 0 total-cost mismatches, 0 non-disjoint results, 0 crashes. An earlier draft of the
verification harness itself had a real bug worth naming: it looked up an edge's weight from a
plain (from, to)-keyed map to compute final path cost, which silently returned the
wrong number whenever the graph had two parallel edges between the same pair of nodes. The fix was
carrying each edge's actual weight alongside the path reconstruction instead of re-deriving it from a
lookup table — the same class of mistake the algorithm itself has to avoid when a genuine edge and a
same-pair reversal edge coexist in the modified graph.
O((V + E) log V) with a heap-based Dijkstra: two Dijkstra calls dominate,
reweighting is a single O(E) pass over the edge list, and cancellation plus path
decomposition is O(V + E). That's the same order as running Dijkstra twice —
nowhere near Yen's O(K · V · (V + E) log V), because there's no per-deviation search:
the second Dijkstra call does the entire job of finding the best possible second path in one pass,
using the reversal trick instead of trying every possible departure point from the first path by
hand. Space: O(V + E) for the modified graph, the same as the input.
This site's guide, Choosing a Shortest-Path Algorithm, compares this entry against the other ten Shortest Paths entries side by side.