Yen's Algorithm, in depth: K shortest loopless paths, root and spur paths, a traced example with ties, tested Python and Lawler's speedup

The problem, stated precisely

Given a directed graph with non-negative edge weights, a source s, a target t and an integer K, return the K cheapest simple paths from s to t: paths that never revisit a node. The word simple matters. If loops were allowed, the second-shortest path in many graphs would be the shortest path with a cheap detour around a two-edge cycle, which is useless for routing. Eppstein's 1998 algorithm solves the loops-allowed version in O(m + n log n + K) time, much faster than anything known for the simple version, but its answers are often unusable for exactly that reason. When people say K shortest paths in practice they nearly always mean the loopless problem, and that is Yen's problem.

Two more properties matter. The output is a ranking, so ties need a rule. And nothing requires the paths to be usefully different: the second-shortest path often shares all but one edge with the first.

The idea: root paths and spur paths

Yen's insight is a statement about where the next path can come from. Suppose you already have the k-1 shortest paths A[1..k-1]. The k-th shortest path, A[k], must agree with some already-found path for a while and then deviate from it. Call the shared prefix the root path and the node where it leaves the spur node. After the spur node, A[k] follows the cheapest possible route to t that does not reuse any root node (it must stay simple) and does not leave the spur node along an edge some known path with the same root already used (otherwise it would be a known path).

That gives a mechanical procedure. For each node i on the most recently accepted path, take the root path up to i, temporarily remove the outgoing edges that known paths sharing that root take from i, temporarily remove the root nodes before i, and run Dijkstra from the spur node to t. Glue root and spur together and you have a candidate. Candidates go into a min-heap B that persists across iterations. After processing every spur node of A[k-1], the cheapest candidate in B is A[k].

Why is it enough to generate spurs only from the newest path? Because spurs from older paths were already generated when those paths were accepted, and their candidates are still waiting in B. The persistent heap is what makes the algorithm correct; forgetting it, and rebuilding B each round, is the most common implementation bug.

Worked example with a three-way tie

Take the graph below with source C and target H. It is small enough to trace and has a property that teaches a lot: three different simple paths cost exactly 8.

k = 1. Plain Dijkstra from C gives A1 = C-E-F-H at cost 2 + 2 + 1 = 5.

k = 2, spurs on A1. Spur at C: the root is just C, and A1 leaves C via C-E, so ban that edge. The best remaining route is C-D-F-H = 3 + 4 + 1 = 8; push it. Spur at E: the root is C-E (cost 2); remove C, ban E-F. From E the options are E-G-H = 5 or E-D-F-H = 6, so push C-E-G-H at 7. Spur at F: root C-E-F (cost 4); remove C and E, ban F-H; F-G-H costs 4, so push C-E-F-G-H at 8. The heap holds 7, 8, 8; pop 7, so A2 = C-E-G-H.

k = 3, spurs on A2. Spur at C: both known paths start C-E, so ban C-E again. The result, C-D-F-H at 8, is already in the heap, so the duplicate check discards it. Spur at E: both known paths share root C-E, and they leave E by E-F and E-G, so ban both. What remains is E-D-F-H = 6, giving candidate C-E-D-F-H at 8. Spur at G: the only edge out of G is banned, so there is no candidate. The heap now holds three paths at 8: C-D-F-H, C-E-F-G-H and C-E-D-F-H.

Which is A3? All three are correct answers. The implementation below breaks ties by insertion order, so it returns C-D-F-H, then C-E-F-G-H, then C-E-D-F-H, then C-D-F-G-H at 11. Another library may order the three 8s differently, or by hop count. If your application cares, make the tie-break explicit: push (cost, hops, sequence, path) instead of (cost, sequence, path), and document it. Tests that compare paths rather than costs will otherwise fail when you swap implementations.

Implementation and a brute-force test

The implementation passes banned nodes and edges into Dijkstra, so the graph itself is never mutated and restored, a classic source of bugs when a spur search returns early.

import heapq, itertools

def dijkstra(adj, s, t, banned_nodes=frozenset(), banned_edges=frozenset()):
    """adj: {u: [(v, w), ...]}, w >= 0. Returns (cost, path) or None."""
    dist, prev, pq = {s: 0}, {}, [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if u == t:
            break
        if d > dist.get(u, float("inf")):
            continue                      # stale heap entry
        for v, w in adj.get(u, ()):
            if v in banned_nodes or (u, v) in banned_edges:
                continue
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v], prev[v] = nd, u
                heapq.heappush(pq, (nd, v))
    if t not in dist:
        return None
    path = [t]
    while path[-1] != s:
        path.append(prev[path[-1]])
    return dist[t], path[::-1]

def yen(adj, s, t, K):
    w = {(u, v): c for u in adj for v, c in adj[u]}
    first = dijkstra(adj, s, t)
    if first is None:
        return []
    A, B, seen, tie = [first], [], {tuple(first[1])}, itertools.count()
    for _ in range(1, K):
        _, last = A[-1]
        for i in range(len(last) - 1):
            spur, root = last[i], last[:i + 1]
            root_cost = sum(w[(root[j], root[j + 1])] for j in range(i))
            banned_edges = {(p[i], p[i + 1]) for _, p in A if p[:i + 1] == root}
            r = dijkstra(adj, spur, t, frozenset(root[:-1]), banned_edges)
            if r is None:
                continue
            cand = root[:-1] + r[1]
            if tuple(cand) not in seen:   # the same path can be found from two spurs
                seen.add(tuple(cand))
                heapq.heappush(B, (root_cost + r[0], next(tie), cand))
        if not B:
            break                         # fewer than K simple paths exist
        cost, _, path = heapq.heappop(B)
        A.append((cost, path))
    return A

Test it against brute force before trusting it. Enumerating every simple path by depth-first search is exponential, but on random graphs of up to seven nodes it is instant, and comparing the sorted cost lists (not the paths, because of ties) catches nearly every bug:

import random

def all_simple_costs(adj, s, t):
    out = []
    def dfs(u, path, cost):
        if u == t:
            out.append(cost); return
        for v, c in adj.get(u, ()):
            if v not in path:
                path.append(v); dfs(v, path, cost + c); path.pop()
    dfs(s, [s], 0)
    return sorted(out)

for _ in range(2000):
    n = random.randint(2, 7)
    adj = {u: [(v, random.randint(1, 5)) for v in range(n)
               if v != u and random.random() < 0.45] for u in range(n)}
    K = random.randint(1, 8)
    got = [c for c, _ in yen(adj, 0, n - 1, K)]
    assert got == all_simple_costs(adj, 0, n - 1)[:K]

Small integer weights are deliberate: they create ties, which is where duplicate handling and banning logic break.

Complexity and the optimizations that matter

Each of the K-1 iterations runs up to n spur searches, one per node of the previous path, and each search is a Dijkstra run costing O(m + n log n) with a binary heap. The total is O(K n (m + n log n)) time. The candidate heap can hold O(K n) paths of up to n nodes, so O(K n^2) memory in the worst case. The useful optimizations all reduce how many spur searches run or how much work each does:

• Lawler's refinement (1972). Spurs before the point where A[k-1] deviated from its parent path regenerate candidates already in the heap. Record each path's deviation index and start the spur loop there. On long paths this skips most of the searches and removes most duplicates.
• Early exit. Stop the spur Dijkstra when it pops t, as the code does. A bidirectional search helps further on large road graphs.
• Bound pruning. If you only need paths no more than a fixed amount above the optimum, discard any spur search whose root cost plus a lower bound exceeds that limit. A reverse Dijkstra from t, run once, gives exact lower bounds for every node.
• Reverse shortest-path tree. With distances to t precomputed, a spur search whose bans miss the tree can simply follow it.

Edge cases

• Undirected graphs. Store each edge in both directions and ban both directions when you ban an edge. Banning only (u, v) lets the spur search walk back along (v, u) and produce a duplicate.
• Parallel edges. If two edges join the same pair of nodes with different weights, the path representation as a node list cannot tell them apart. Represent paths as edge-id lists instead.
• Negative weights. Dijkstra requires non-negative weights. With negative weights but no negative cycles, use Bellman-Ford or reweight once with Johnson's potentials; reweighting preserves the ranking of paths between the same pair, so Yen runs unchanged on the reduced costs.
• Fewer than K paths. Small or sparse graphs may have fewer than K simple paths. Return what exists instead of raising, as the code does when B empties.
• Floating-point costs. Summed floats make ties unstable; use integer units such as metres.

Failure modes

The bugs that survive code review usually look like one of these:

• Rebuilding the heap each iteration. The output silently skips paths. The brute-force test catches it within a few hundred trials.
• Banning only the edge of the previous path. You must ban the next edge of every known path that shares the current root, or the spur search rediscovers A[1] from a later spur.
• Forgetting to remove root nodes. The candidate loops back through the root, so it is not simple.
• No duplicate check. The same candidate is reachable from different spurs of different paths. Without a seen-set it is emitted twice and occupies two of your K slots.
• Unbounded K on a large graph. K = 1,000 on a continental road graph means hundreds of thousands of Dijkstra runs. Put a limit on K and a time budget on the request.

When to use it and when not to

Yen is the right tool when you need exact, ranked, loopless paths and K is modest: tens, sometimes low hundreds. Typical uses are backup routes in traffic engineering, and candidate generation for routing with a constraint that cannot be expressed as an edge weight: generate paths in cost order and return the first that passes.

It is the wrong tool in three common situations. If the constraint is additive, such as a budget on a second resource, a resource-constrained shortest path label-setting algorithm is usually far faster than enumerating until one fits. If you need paths that share no edges, for protection against a single link failure, Suurballe's algorithm finds an optimal disjoint pair directly. If you need alternatives a person would see as different, ranked shortest paths disappoint: the top ten may all differ by one side street. Route planners instead use penalty methods (raise the weight of edges on accepted paths and re-search), plateau methods, or via-node methods with an explicit limit on overlap.

Trade-offs

What to do next

To turn this into working knowledge:

1. Trace the six-node example yourself, then add an edge D-G of weight 1 and predict the new ranking before running the code.
2. Run the implementation and the brute-force harness together; then deliberately break one ban rule and watch the test fail.
3. Add Lawler's deviation index and count how many Dijkstra runs it saves on a 1,000-node random graph with K = 20.
4. Compare your output with NetworkX's shortest_simple_paths on the same graph, matching costs rather than paths.
5. Review Dijkstra's algorithm for the inner search, Bellman-Ford for negative weights, Suurballe's algorithm for disjoint paths, and constrained shortest paths for when a resource limit is the real requirement.