How to Learn Eppstein’s K-Shortest-Paths Algorithm: Shortest-Path Trees, Sidetrack Costs, Persistent Heaps and Path Enumeration

Quick Read. Eppstein’s algorithm answers a richer question than ordinary shortest path: after the best route, what are the next best routes, and the next? The beginner should first master Dijkstra and shortest-path trees. The intermediate learner should understand sidetrack edges and their extra cost above the shortest route. The advanced learner should see how persistent heaps compress all legal sidetrack choices. The professional must distinguish walks from simple paths, understand output-sensitive enumeration, choose a practical alternative when simplicity constraints matter, and test path ordering and duplicate behaviour carefully.

One-sentence answer

Eppstein’s algorithm preprocesses a graph around one shortest-path tree, assigns every non-tree edge a nonnegative sidetrack penalty, and then enumerates increasingly costly combinations of sidetracks using heap-ordered structure instead of recomputing a shortest path from scratch each time.

Why k shortest paths is a different problem

A shortest-path algorithm gives one optimal route. Real systems often need alternatives: a navigation service may want several routes, a network planner may need fallback paths, a language system may keep multiple hypotheses, and a search pipeline may want the best k candidates rather than only the winner.

The naive strategy is to find the shortest path, forbid something about it, run another shortest-path computation, and repeat. That can throw away enormous amounts of reusable structure. Eppstein’s key idea is to compute the shortest-path geometry once and represent every alternative by the sidetracks it takes away from that geometry.

Level 1 — Beginner: start from one destination

Fix a source s and target t. Compute d(v), the shortest distance from every vertex v to t. With nonnegative edge weights this can be done by running Dijkstra on the graph with edges reversed. Choose, for every reachable vertex except t, one outgoing edge that continues along a shortest route to t. Those chosen edges form a shortest-path tree directed toward t.

If you start at any vertex and follow the tree edges, you eventually reach t along a shortest route. The tree therefore acts as the default route. An alternative path is created whenever you leave this default using a non-tree edge and later return to tree-guided travel.

The sidetrack cost

For an edge e = (u,v) with weight w(e), define

delta(e) = w(e) + d(v) - d(u)

Because d(u) is the shortest possible cost from u to t, taking e and then following a shortest route from v cannot be cheaper. Therefore delta(e) is nonnegative. For a chosen shortest-path-tree edge, delta is zero. For a genuine sidetrack, delta measures how much extra cost that deviation introduces relative to staying on a shortest route.

This turns path ranking into a much cleaner problem. The total length of an s-to-t route is the shortest distance d(s) plus the sum of the penalties of the sidetracks it uses, provided the sidetracks occur in a compatible order along the resulting route.

A small example

Imagine the shortest route s → a → b → t has cost 10. There is a non-tree edge from a to c whose weight plus the best c-to-t continuation makes the resulting route cost 12. That sidetrack has penalty 2. Another sidetrack later in the route adds 3. A route using both has base cost 10 plus those compatible extra costs.

For learning, label every edge in a small graph with both its original weight and its sidetrack penalty. The graph often becomes easier to reason about after this reweighting because the optimal tree has zero extra cost and every departure has an explicit price.

Level 2 — Intermediate: why heaps appear

At a vertex v, there may be several outgoing sidetracks. We would like quick access to the cheapest one. More importantly, while travelling from v toward t along the shortest-path tree, we want access to sidetracks that leave from any vertex on that tree path.

Eppstein constructs heap structures that collect these sidetrack possibilities. Conceptually, each vertex owns a heap of non-tree edges leaving that vertex, ordered by delta. Then the algorithm builds a persistent accumulated heap for the entire tree path from that vertex to t. Persistence matters because neighbouring vertices share most of the same suffix toward t; copying the whole heap at every vertex would destroy the efficiency.

You do not need to implement persistence on day one. First build the conceptual version using ordinary lists of available sidetracks on small graphs. Once you can enumerate the alternatives correctly, replace repeated copied structures with shared persistent heaps.

From sidetrack choices to a heap-ordered search space

The deepest step is that possible routes can themselves be organised into a heap-like tree. The root represents the shortest path with no sidetracks. Children represent ways to make the current sidetrack choice more expensive or to append a later compatible sidetrack. Edge weights in this auxiliary structure correspond to additional sidetrack cost.

Once this implicit tree of alternatives is heap ordered, k-best enumeration becomes a best-first traversal problem: repeatedly take the cheapest not-yet-output route representation and expose its children. The algorithm avoids rebuilding full paths until an output path is actually needed.

preprocess distances d(v) to target t
choose a shortest-path tree T
compute delta(e) for every sidetrack edge
build shared heaps of sidetrack choices

priority_queue.push(shortest_path_representation)
repeat k times:
    p = priority_queue.pop_min()
    output/materialize p
    push p's next valid sidetrack alternatives

This pseudocode hides the clever heap construction, but it reveals the architecture: one shortest-path preprocessing phase followed by cheap incremental enumeration.

Level 3 — Advanced: the output-sensitive bound

Eppstein’s 1998 SIAM Journal on Computing paper gives O(m + n log n + k) time for the directed k-shortest-path problem under the paper’s model, with paths not required to be simple. The preprocessing is dominated by shortest-path computation and heap construction; after that, the representation supports constant amortised work per additional output in the theoretical bound.

The phrase not required to be simple is critical. A path in this formulation may repeat vertices or edges. In many textbooks and software libraries, “path” is reserved for vertex-simple routes, while other literature may call repeated-vertex objects walks. A professional must verify the problem definition before choosing an algorithm.

Eppstein versus Yen

Yen’s classic algorithm targets k shortest loopless or simple paths. It repeatedly creates spur-path subproblems and is conceptually easier to implement. Current NetworkX documentation for shortest_simple_paths uses Yen’s method, and current SciPy also exposes a Yen implementation.

Eppstein’s method is theoretically elegant and extremely efficient for its non-simple-path formulation, but it is substantially more complex to implement. The correct choice depends on the contract: do repeated vertices matter, how large is k, how frequently is the graph reused, and is implementation simplicity more valuable than the strongest theoretical bound?

Correctness: the three facts to prove

Nonnegative penalties: every sidetrack has delta ≥ 0 because d(u) is already shortest.
Representation: every admissible s-to-t route can be described by an ordered sequence of compatible sidetracks plus shortest-tree segments between them.
Ordering: the auxiliary heap structure exposes route representations in nondecreasing total sidetrack penalty, so adding d(s) preserves nondecreasing path length.

These facts are the intellectual spine. Persistent heaps and pointer machinery exist to make those facts computationally cheap, not to replace them.

Professional engineering decisions

Define route semantics: simple path, walk, edge-simple trail and bounded-cycle route are different problems.
Handle ties: many routes may have identical cost; define stable or deterministic tie-breaking if reproducibility matters.
Materialise lazily: store compact sidetrack representations and reconstruct full vertex sequences only when needed.
Control duplicate representations: implementation details must ensure the auxiliary search does not emit the same route more than intended.
Validate numeric range: distance and delta calculations can overflow fixed-width integers.
Separate preprocessing from query cost: Eppstein becomes more attractive when many outputs or repeated queries reuse the same structure.

Testing ladder

A graph with exactly one s-to-t route.
Two equal-cost alternatives.
A graph where the second-best route uses one sidetrack.
A graph where a later route uses multiple compatible sidetracks.
Parallel edges if the graph model permits them.
Zero-weight edges.
Cycles that create non-simple alternatives.
Small random graphs enumerated exhaustively and sorted by cost as a reference oracle.

Exhaustive enumeration is practical only for tiny graphs, but those tiny graphs are exactly where it is most useful. Generate all bounded routes or all simple paths according to your contract, sort them independently, and compare the first k outputs from the fast algorithm.

Common misconceptions

“Just run Dijkstra k times.” That discards reusable structure and does not by itself define how previous answers are excluded.
“Sidetrack cost is the edge weight.” It is the extra cost relative to the shortest continuation.
“k shortest always means k shortest simple paths.” Eppstein’s classic bound is for paths that may repeat vertices and edges.
“Persistent heaps are the idea.” The core idea is representing alternatives as priced deviations from one shortest-path tree; persistence makes that representation efficient.
“The second path differs by one edge.” The ranking is by total cost, not structural similarity.

A learning route from beginner to professional

Beginner: compute a shortest-path tree to one target and verify d(u) ≤ w(u,v)+d(v).
Intermediate: calculate sidetrack penalties and rank all one-sidetrack alternatives by hand.
Advanced: trace compatible sequences of sidetracks and build a simplified heap of route candidates.
Algorithm engineer: implement structural sharing for the accumulated sidetrack heaps and lazy path reconstruction.
Professional: compare Eppstein with Yen and domain-specific alternatives using the exact route contract, k distribution, graph size and reuse pattern of the application.

For teaching, stage the representation change. First predict the next-best route from a drawing. Then run the shortest-path tree. Investigate why delta is nonnegative. Modify one edge weight and observe which sidetrack becomes attractive. Only then introduce the persistent heap machinery. Worked examples should fade from full route diagrams to compact sidetrack sequences as the learner’s mental model strengthens.

Authoritative sources and further reading

D. Eppstein, Finding the k Shortest Paths, SIAM Journal on Computing 28(2), 1998.
David Eppstein’s publication page for Finding the k Shortest Paths, including paper and implementation links.
J. Y. Yen, Finding the K Shortest Loopless Paths in a Network, Management Science, 1971.
NetworkX shortest_simple_paths documentation, a practical Yen-based reference for simple paths.
S. Sentance, J. Waite and M. Kallia, Teachers’ Experiences of Using PRIMM to Teach Programming in School, SIGCSE 2019.
C. Szabo et al., Parsons Problems and Computing Education Learning Theories, Koli Calling 2025.

Closing idea. Eppstein’s algorithm teaches a sophisticated but widely useful design pattern: solve the optimal case once, measure every deviation from it, and enumerate alternatives by the extra price of leaving the optimum.