The site's eighth Shortest Paths entry, and the first to answer a different
question than the other seven. Dijkstra's Algorithm and the
rest all answer "what's the cheapest path?" — one path, one number. Yen's algorithm asks for
the K cheapest loopless (no repeated node) paths, ranked. That's a genuinely
different job: a routing engine that only ever offers the single optimum has nothing to say if that
road is closed, and a network operator planning backup capacity needs to know the second- and
third-best routes exist at all, not just that one route is best. Yen's algorithm doesn't replace
Dijkstra — it calls Dijkstra (or any single-source shortest-path routine) over and over, each time
with a slightly different graph, and assembles the K-path ranking from what those calls return.
Path 1 is free: plain Dijkstra from source to target. Path 2 has to differ from path 1 somewhere
— the algorithm tries every possible point of departure and keeps the cheapest result. For each node
i along path 1, split the path into a root path (source through node
i, kept fixed) and everything after. Node i becomes the spur
node: temporarily delete the specific edge that path 1 used to leave it (so the search is
forced to try something else) and delete every other node the root path already passed through (so
the new tail can't loop back and revisit them), then run Dijkstra again from the spur node to the
target on what's left. Splice the root path back onto whatever that restricted search finds, and the
result is one candidate for path 2. Doing this once per node on path 1 produces a small batch of
candidates; the cheapest one becomes path 2, and the rest wait in a candidate pool. Path 3 repeats
the same process, deviating from path 2 instead — reusing any leftover candidates from path 2's own
round if they're still valid — and so on.
Six waypoints, nine one-way trails (this is the classic textbook example for the algorithm). Choose how many paths to rank (1–7 — there are only seven simple loopless paths from C to H in this graph, so anything past 7 just stops early) and press Step or Run. Root-path edges plus every already-accepted path glow orange; a black bordered node is the current spur node; grey dashed edges are the ones blocked for that specific attempt (either path 1's own choice, or an earlier accepted path's, at that same root); the black, extra-thick edges are the freshly built candidate under consideration right now. Watch paths 3, 4, and 5 all land on the same cost (8) — a real tie, not a bug — and watch what happens once K exceeds 7: the candidate pool runs dry and the algorithm just stops, having enumerated every loopless path there is.
accepted paths, ranked (A):
candidates waiting, cheapest first (B):
Two things have to be true for this to actually enumerate the K cheapest loopless paths in order, and both are checkable in the demo above.
No candidate is ever missed. Whatever path k+1 turns out to be, it
must diverge from path k — the path just before it in the ranking — at some node,
because if it agreed with path k everywhere it would just be path k.
Trying every possible divergence point along path k (every spur node) is exhaustive by
construction: one of those attempts necessarily reconstructs the true next-cheapest path, so it's
guaranteed to land in the candidate pool before path k+1 is chosen from it.
No candidate is ever a repeat. Deleting the specific edge that an already-accepted path used to leave a shared root stops the search from silently rediscovering that same accepted path again under a new name — the whole point of deviating is to find something different. Deleting the rest of the root's interior nodes (not just that one edge) is what keeps every candidate loopless: without it, the tail search is free to route back through an earlier node on the root path, producing a walk that revisits a node rather than a genuine simple path. Both deletions are undone before the next spur attempt — they only apply to the one restricted search that needs them.
General adjacency-list version — edges maps a node to a list of
[neighbor, weight] pairs, matching every other graph algorithm on this site:
function dijkstraRestricted(nodes, edges, source, target, removedNodes, removedEdges) {
const dist = new Map(nodes.map(n => [n, Infinity]));
const prev = new Map();
dist.set(source, 0);
const visited = new Set();
while (true) {
let u = null, best = Infinity;
for (const n of nodes) {
if (!visited.has(n) && !removedNodes.has(n) && dist.get(n) < best) { best = dist.get(n); u = n; }
}
if (u === null) break;
visited.add(u);
if (u === target) break;
for (const [v, w] of (edges.get(u) || [])) {
if (removedNodes.has(v) || removedEdges.has(u + '->' + v)) continue;
const nd = dist.get(u) + w;
if (nd < dist.get(v)) { dist.set(v, nd); prev.set(v, u); }
}
}
if (dist.get(target) === Infinity) return null;
const path = [target];
while (path[path.length - 1] !== source) {
const p = prev.get(path[path.length - 1]);
if (p === undefined) return null;
path.push(p);
}
return path.reverse();
}
function pathCost(edges, path) {
let cost = 0;
for (let i = 0; i < path.length - 1; i++) {
cost += edges.get(path[i]).find(([v]) => v === path[i + 1])[1];
}
return cost;
}
function yenKSP(nodes, edges, source, target, K) {
const first = dijkstraRestricted(nodes, edges, source, target, new Set(), new Set());
if (!first) return [];
const A = [{ path: first, cost: pathCost(edges, first) }];
const B = [];
const seen = new Set([first.join(',')]);
for (let k = 1; k < K; k++) {
const prevPath = A[k - 1].path;
for (let i = 0; i < prevPath.length - 1; i++) {
const spurNode = prevPath[i];
const rootPath = prevPath.slice(0, i + 1);
const removedEdges = new Set();
for (const { path } of A) {
if (path.length > i && rootPath.every((n, idx) => path[idx] === n)) {
removedEdges.add(path[i] + '->' + path[i + 1]);
}
}
const removedNodes = new Set(rootPath.slice(0, i));
const spurPath = dijkstraRestricted(nodes, edges, spurNode, target, removedNodes, removedEdges);
if (spurPath) {
const totalPath = rootPath.slice(0, -1).concat(spurPath);
const key = totalPath.join(',');
if (!seen.has(key)) {
seen.add(key);
B.push({ path: totalPath, cost: pathCost(edges, totalPath) });
}
}
}
if (B.length === 0) break; // exhausted every loopless path — fewer than K exist
B.sort((x, y) => x.cost - y.cost);
A.push(B.shift());
}
return A;
}Skipping the node exclusion — blocking only the matching edge — produces paths with
repeated nodes. This was checked directly, not just reasoned about: a variant that deletes
removedEdges but leaves removedNodes empty was run against 5,000 random
directed graphs and found a concrete failure inside the first handful of trials — on a 6-node graph,
requesting K = 4 paths from N0 to N5, the buggy version
returned N0 → N3 → N2 → N0 → N5 as a "path," revisiting N0. The root cause
is exactly what Why it works above predicts: with only the one edge gone, the
restricted search from the spur node is still completely free to route back through any earlier root
node it likes.
Ties are real and the tie-break is arbitrary. On the demo's own graph, paths 3,
4, and 5 all cost exactly 8 — C→D→F→H, C→E→F→G→H, and
C→E→D→F→H. The reference implementation's stable sort happens to settle ties in
insertion order into B, which is itself an artifact of iteration order over the spur
nodes, not a meaningful preference between the three routes. Anything downstream that treats "path 3"
as strictly better than "path 4" because of list position, when both cost the same, is reading
significance into a coin flip.
Requesting more paths than exist doesn't error — it just quietly returns fewer.
This graph has exactly seven simple loopless paths from C to H; ask for K = 7 (the demo's own upper
bound) and the candidate pool B goes empty right after the seventh is accepted, so the
loop above breaks early rather than looping forever or throwing. A caller that assumes the return
value always has exactly K entries — instead of checking its actual length — will
silently under-count once the graph is small (or dense-enough-of-a-bottleneck) relative to the K it
asked for.
It's meaningfully more expensive than the shortest-path search it's built on. See Complexity below — every additional path can cost up to a full extra pass of Dijkstra-like searches, one per node on the previous path, not one more unit of work.
O(K · V · (V + E) log V) with a heap-based Dijkstra: finding each of the K paths
after the first can require up to V spur-node attempts (one per node on the previous
path), and each attempt is a full restricted Dijkstra search costing O((V + E) log V).
The array-backed version the demo and reference code above use is O(K · V · (V² + E))
instead, for the same reason Dijkstra's own array-backed queue costs more per extraction — see Dijkstra's own page. Space:
O(K · V) to store the K accepted paths, plus whatever candidates are waiting in
B at any moment (at most V per round).
This site's guide, Choosing a Shortest-Path Algorithm, compares this entry against the other ten Shortest Paths entries side by side.