Yen's Algorithm

Purpose: Find the $K$ shortest loopless paths from a source to a target in a directed graph with non-negative weights, in $O(KV(E+V\log V))$.

Algorithm

1. Compute the shortest path $A_1$ with Dijkstra. Put it in the result list $A$.
2. For $k=2\dots K$:
   • For each node $A_{k-1}[i]$ on the previous path (the spur node), with $\text{root}=A_{k-1}[\mathrm{0..}i]$:
     • Remove every edge $A_j[i]\to A_j[i+1]$ for each already-found path $A_j$ sharing the same root prefix. This forbids re-deriving a known path.
     • Remove every node of the root path except the spur node itself. This forbids loops.
     • Run Dijkstra from the spur node to the target. If a path is found, the candidate is $\text{root}+\text{spur path}$; add it to a candidate set $B$ (a min-heap keyed by total cost).
     • Restore the removed edges and nodes.
   • If $B$ is empty, stop — fewer than $K$ paths exist. Otherwise move the cheapest candidate from $B$ to $A$.

Code sketch

vector<Path> yen(int s, int t, int K) {
    vector<Path> A;
    A.push_back(dijkstraPath(s, t));
    if (A[0].empty()) return {};
    set<pair<long long, Path>> B;                 // candidates, ordered by cost
 
    for (int k = 1; k < K; k++) {
        const Path& prev = A[k - 1];
        for (int i = 0; i + 1 < (int)prev.size(); i++) {
            int spur = prev[i];
            Path root(prev.begin(), prev.begin() + i + 1);
 
            vector<Edge> removedE; vector<int> removedV;
            for (const Path& p : A)
                if (p.size() > i && equalPrefix(p, root, i + 1))
                    removedE.push_back(removeEdge(p[i], p[i + 1]));
            for (int j = 0; j < i; j++) removedV.push_back(removeNode(root[j]));
 
            Path spurPath = dijkstraPath(spur, t);
            if (!spurPath.empty()) {
                Path total = root; total.pop_back();
                total.insert(total.end(), spurPath.begin(), spurPath.end());
                B.insert({cost(total), total});
            }
            restore(removedE, removedV);
        }
        if (B.empty()) break;
        A.push_back(B.begin()->second);
        B.erase(B.begin());
    }
    return A;
}

Paradigm

Deviation / branch enumeration. Every $k$-th shortest path must deviate from one of the first $k-1$ paths at some node; Yen’s enumerates exactly those deviations and takes the best.

Complexity

• Time: $O(KV(E+V\log V))$ — up to $V$ spur nodes per round, each costing a Dijkstra
• Space: $O(KV+E)$

Why It Works

Claim: the $k$-th shortest loopless path shares a (possibly empty) prefix with one of $A_1,\dots ,A_{k-1}$ and then deviates.

Any path that shares no prefix with $A_1$ still shares the source, i.e. deviates at index 0 — which is a spur node the algorithm tries. Since the algorithm generates, for every already-found path and every deviation point, the cheapest continuation avoiding known paths and loops, the true $k$-th path is always present in $B$ when it is needed. Taking the minimum of $B$ therefore yields it. ∎

Variants / Use Cases

• Eppstein’s algorithm — $O(E+V\log V+K)$ but allows loops; strictly faster when loopy paths are acceptable
• Suurballe’s algorithm — $k$ vertex-disjoint paths, a different requirement
• Network routing with backup paths, transit itineraries, k-best alignments in bioinformatics
• k-shortest walks in a DAG — much simpler: a DP keeping the best $k$ values per node
• Lawler’s modification — avoids redundant spur computations by remembering the deviation index; a constant-factor improvement worth having