The site's twelfth Shortest Paths entry, and a direct extension of Suurballe's Algorithm: that page's own Pitfalls section names the gap and leaves it explicitly unbuilt — "edge-disjoint is not vertex-disjoint," and a caller who actually needs a backup route immune to one node failing, not just one link, needs something more. This page builds that something more, and it turns out to need no new search algorithm at all — just a graph transformation in front of the algorithm that already exists.
Suurballe's own demo page works a small, deliberately constructed example: two paths,
S→X→A→T and S→Y→X→T, that share zero edges and are confirmed optimal
against brute force — but both pass through node X. For a link failure, that's a
perfectly good disjoint pair. For a node failure — a router going down, not just a cable — it's
useless: lose X and both "backup" paths die at once. The question this page answers is
the strictly harder one: find two paths from source to target, minimizing combined cost, that share
no vertex at all except the source and target themselves.
The fix, usually credited to Suurballe and Tarjan's own 1984 follow-up paper, is a
node-splitting transform: split every node except the source and target into an
in-copy and an out-copy, joined by a single edge of cost zero.
Every original edge (u, v) becomes (uout, vin) in
the transformed graph. Now the only way to pass all the way through a node is to cross its one
in→out edge — so if two paths ever try to share that node, they collide on that shared edge, and
edge-disjointness (which Suurballe's algorithm already guarantees) becomes vertex-disjointness for
free. No new search logic; the exact same suurballe() call from the previous page runs
unmodified on the transformed graph.
Same five stops as Suurballe's own demo — S, X, A,
Y, T — and the same edge weights, so the first two steps below should look
familiar: the cheapest edge-disjoint pair really does share X. From there, watch every
node except S and T split into an in/out pair
(dotted zero-cost edge between them), Suurballe's algorithm run once on that bigger graph, and the
result collapse back onto the original five stops as two paths that share nothing but the endpoints
— at one extra unit of cost.
The split edge is the only door through a node, and Suurballe's algorithm already refuses
to use one door twice. In the transformed graph, every real edge lands on an
out-copy's outgoing side and an in-copy's incoming side — there is no way
to arrive at a node and leave it again without crossing that node's own in→out edge,
because that's the only edge connecting the two halves. Suurballe's algorithm returns two paths
guaranteed to share no edge in whatever graph it's given; apply it to a graph where "passing through
node v" and "using edge vin→vout" are the same event,
and edge-disjointness and vertex-disjointness become the same guarantee.
The split edge has to cost exactly zero, or the algorithm silently starts optimizing a different problem. Suurballe's algorithm minimizes total edge weight along both paths combined; giving every crossed node a nonzero toll would mean the "cheapest vertex-disjoint pair" it finds is cheapest under a cost function that includes made-up per-node charges, not the original edge weights the caller actually cares about. Zero-cost keeps the objective identical to the original problem — it exists purely to give the algorithm's own edge-disjointness machinery something to collide on, not to change what "cheapest" means.
Source and target don't get split, because they don't need the guarantee. Both
returned paths visit S and T exactly once each, by definition — every
source-to-target path starts at S and ends at T. There's nothing to
protect against: two paths "sharing" their own shared endpoints isn't a failure mode, it's the
question's own premise. Splitting them anyway doesn't just add unneeded bookkeeping — see the first
pitfall below for what actually goes wrong.
The transform, plus the exact suurballe()/dijkstra()/
reconstructEdges() functions from the previous page,
unmodified — only the graph handed to them changes:
// nodes: array of node ids. edges: [{a, b, w}, ...]. source/target are NOT split.
function splitGraph(nodes, edges, source, target) {
const tNodes = [];
const tEdges = [];
const inId = n => n + '_in', outId = n => n + '_out';
for (const n of nodes) {
if (n === source || n === target) { tNodes.push(n); continue; }
tNodes.push(inId(n), outId(n));
tEdges.push({ a: inId(n), b: outId(n), w: 0 }); // the one door through n
}
const outSide = n => (n === source || n === target) ? n : outId(n);
const inSide = n => (n === source || n === target) ? n : inId(n);
for (const { a, b, w } of edges) {
tEdges.push({ a: outSide(a), b: inSide(b), w });
}
return { tNodes, tEdges };
}
// collapse a transformed path back to original node ids, dropping consecutive
// duplicates (an in-copy immediately followed by its own out-copy).
function collapsePath(path) {
const out = [];
for (const p of path) {
const base = p.endsWith('_in') ? p.slice(0, -3) : p.endsWith('_out') ? p.slice(0, -4) : p;
if (out.length === 0 || out[out.length - 1] !== base) out.push(base);
}
return out;
}
// nodes/edges: original graph. Returns { path1, path2, totalCost } in original node ids, or null.
function vertexDisjointPaths(nodes, edges, source, target) {
const { tNodes, tEdges } = splitGraph(nodes, edges, source, target);
const result = suurballe(tNodes, tEdges, source, target); // unmodified from Suurballe's page
if (!result) return null;
return {
path1: collapsePath(result.path1),
path2: collapsePath(result.path2),
totalCost: result.totalCost,
};
}Splitting the source or target too doesn't just add unnecessary work — it breaks the
algorithm outright. If S gets split like every other node, both returned paths
have to leave through the single edge Sin→Sout — but
edge-disjointness forbids using that edge twice, so the second path can't leave S at
all, and the search reports no path exists. On the demo's own graph, the correct answer (cost 9,
routing around X) exists and is found; splitting S and T as
well turns that into null instead. This isn't a one-off on this particular graph:
across 5,740 random directed graphs (5-7 nodes) where a genuine vertex-disjoint pair exists, splitting
the endpoints reported "impossible" in 100% of them — not occasionally worse, always
wrong, because the source only ever has the one door out regardless of how many real edges leave it.
Wiring the transform's edges to bypass the split door lets two paths share a node without
either of them ever touching the edge that's supposed to catch it. The transform above
routes every original edge as out-copy → in-copy; a plausible-looking variant that
instead wires edges as in-copy → in-copy (or out-copy → out-copy) still
produces a graph Suurballe's algorithm happily runs on and returns two genuinely edge-disjoint paths
for — the bug is silent, not a crash. But if every original edge lands on the in-copy at
both ends, a path can walk straight through a node's in-copy and out again on another
in-copy edge without ever crossing that node's own zero-cost door, so two different
paths can each do this through the same node and never collide. On the demo's graph, this
variant reproduces plain edge-disjoint Suurballe's original answer exactly — cost 8, both paths
routed through X — silently giving up the entire guarantee this page exists to add.
Checked against 5,740 random graphs with a genuine solution: this miswiring shares a vertex in 31 of
them (0.54%) — rare on unstructured random graphs, because most don't have a real "chokepoint" node
worth exploiting, which is exactly why the demo's graph was built by hand around one rather than
found by random search.
Verification: the reference implementation above was checked against brute-force enumeration of every simple path pair (filtering for shared interior vertices, not shared edges) on 3,000 random directed graphs (5-7 nodes, sparse), 0 total-cost mismatches across every case where a vertex-disjoint pair existed at all — including agreement on the 2,116-of-3,000 cases (correctly) reporting none exists. Both pitfall variants above were checked against the same graph set, not just the hand-built demo example, before writing the percentages down.
O((V + E) log V) — identical to plain Suurballe's algorithm, run once on the
transformed graph. The transform itself is a single O(V + E) pass that at most doubles
the node count (every node but two gains a partner) and adds at most V - 2 new
zero-cost edges to the existing E, so the transformed graph's own V and
E stay within a small constant factor of the original — same asymptotic class, more
nodes and edges for the same two Dijkstra calls to walk. Space: O(V + E)
for the transformed graph, same reasoning.
This site's guide, Choosing a Shortest-Path Algorithm, compares this entry against the other eleven Shortest Paths entries side by side.