Eppstein's Algorithm

Purpose: Find the $K$ shortest paths (loops allowed) from $s$ to $t$ in $O(E+V\log V+K\log K)$ — asymptotically optimal, and vastly faster than Yen’s when $K$ is large.

The Idea

1. Compute the shortest-path tree to $t$ (Dijkstra on the reversed graph), giving $d(v)$ = distance from $v$ to $t$.
2. Define the sidetrack cost of an edge $u\to v$:
   $\delta (u\to v)=w(u,v)+d(v)-d(u)\ge 0.$
   Tree edges have $\delta =0$. Any $s\to t$ path is the shortest path plus a sequence of sidetrack edges, and its length is $d(s)+\sum \delta$.
3. So the problem becomes: enumerate sets of sidetrack edges in increasing total $\delta$. This is a $K$-smallest-sums problem.
4. Eppstein builds a path graph $P(G)$: a heap-ordered DAG whose nodes are sidetrack edges, with out-degree 4 and where a path from the root corresponds to a valid sidetrack sequence. Running a $K$-smallest search (a heap-based best-first traversal) on $P(G)$ yields the answer in $O(K\log K)$.

The heavy machinery is step 3-4: a persistent leftist/ randomized heap per vertex, where each vertex’s heap is its parent’s heap plus its own outgoing sidetracks. Persistence is what keeps the total size $O(E\log V)$ rather than $O(VE)$.

Simplified practical version

Most contest problems accept a much simpler $O(K\log K\cdot \text{something})$ variant that skips the path-graph construction entirely:

// K shortest s->t walks, loops allowed. d[] = distance to t (reverse Dijkstra).
vector<long long> kShortest(int s, int t, int K) {
    vector<long long> res;
    vector<int> cnt(n, 0);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    pq.push({d[s], s});                       // A*-style: key = g + h
    while (!pq.empty() && (int)res.size() < K) {
        auto [cost, u] = pq.top(); pq.pop();
        if (cnt[u] >= K) continue;
        cnt[u]++;
        if (u == t) res.push_back(cost);
        for (auto [v, w] : adj[u])
            pq.push({cost - d[u] + w + d[v], v});
    }
    return res;
}

This is $K$-times-A* with the consistent heuristic $h(v)=d(v)$: it pops each vertex at most $K$ times, and the $i$-th pop of $t$ is the $i$-th shortest walk. Simple, correct, and fast enough for typical $K\le 10^5$.

Complexity

Version	Time	Loops?
Full Eppstein (path graph)	$O(E+V\log V+K\log K)$	allowed
A*-with-counters (above)	$O((E+KV)\log (\cdot ))$	allowed
Yen	$O(KV(E+V\log V))$	forbidden

Paradigm

Reduction to a $K$-smallest-sums problem over a heap-ordered structure, plus a potential function ($d(v)$) that makes every edge non-negative — the same reweighting trick as Johnson’s algorithm.

Variants / Use Cases

• When you need loopless paths — use Yen; Eppstein’s output may repeat vertices
• K shortest paths in a DAG — trivial DP, no need for either algorithm
• Route planning with alternatives, k-best parses / alignments, network resilience analysis
• Second shortest path ($K=2$) — a single Dijkstra pair (forward and reverse) plus an edge scan is enough; don’t reach for Eppstein