viii. K Shortest and Disjoint Paths

Three different problems:

• $k$ shortest walks (vertices may repeat): pop each vertex up to $k$ times in Dijkstra, $O(km\log )$; or Eppstein’s sidetrack heaps, $O(m\log m+k\log k)$.
• $k$ shortest simple paths: Yen’s algorithm, $O(kn(m\log n))$.
• $k$ disjoint paths of minimum total cost: min-cost flow of value $k$ (Suurballe for $k=2$); “shortest, then delete it, then shortest again” is wrong.

$k$ shortest walks by repeated popping

vector<ll> kWalks(const vector<vector<pair<int, ll>>>& g, int s, int t, int k) {   // CSES Flight Routes
    vector<int> cnt(sz(g)); vector<ll> res;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; pq.push({0, s});
    while (sz(pq) && sz(res) < k) {
        auto [d, u] = pq.top(); pq.pop();
        if (cnt[u]++ >= k) continue;
        if (u == t) res.push_back(d);
        for (auto [v, w] : g[u]) pq.push({d + w, v});
    }
    return res;
}

Proof: the $i$-th pop of $v$ is the $i$-th shortest walk to $v$

Claim: every one of the $k$ shortest walks to any vertex $v$ is generated, i.e. all its prefixes are among the first $k$ pops of their endpoints. Suppose a walk $W$ among the $k$ shortest to $v$ has a prefix $W^{\prime }$ (ending at $u$) that is not among the $k$ shortest walks to $u$. Then there are $k$ walks to $u$ no longer than $W^{\prime }$; appending $W$‘s remaining suffix to each gives $k$ distinct walks to $v$, all different from $W$ and no longer than it, contradicting that $W$ is among the $k$ shortest. Since weights are nonnegative, the heap pops walks to each vertex in nondecreasing length, so the $i$-th pop of $t$ is the $i$-th shortest walk. Each vertex is expanded at most $k$ times: $O(km\log (km))$.

Eppstein: sidetrack heaps

Compute $d(v)$ = distance from $v$ to $t$ and the shortest-path tree towards $t$. For a non-tree edge $e=(u\to v,w)$ the sidetrack cost is $\delta (e)=w+d(v)-d(u)\ge 0$. Every $s$–$t$ walk is the tree path with a sequence of sidetracks, and its length is $d(s)+\sum \delta$. Store, for every vertex $u$, a persistent leftist heap $H(u)$ of all sidetracks leaving the tree path from $u$ to $t$: $H(u)=H(\text{next}(u))\cup \{\text{sidetracks out of }u\}$. A best-first search over these heaps enumerates walks in order.

vector<ll> eppstein(int n, const vector<array<ll, 3>>& E, int s, int t, int k) {   // edges u -> v, w >= 0
    const ll INF = LLONG_MAX / 4;
    vector<vector<pair<int, int>>> rg(n);                       // reversed: (from, edge id)
    for (int i = 0; i < sz(E); i++) rg[E[i][1]].push_back({(int)E[i][0], i});
    vector<ll> d(n, INF); vector<int> tree(n, -1), order;      // tree[u]: edge u -> next(u)
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; d[t] = 0; pq.push({0, t});
    while (sz(pq)) {
        auto [du, u] = pq.top(); pq.pop(); if (du != d[u]) continue; order.push_back(u);
        for (auto [v, e] : rg[u]) if (du + E[e][2] < d[v]) d[v] = du + E[e][2], tree[v] = e, pq.push({d[v], v});
    }
    if (d[s] >= INF) return {};
    struct Node { ll key; int to, l, r, rk; };
    vector<Node> T{{0, 0, 0, 0, 0}};                           // node 0 = empty heap
    auto merge = [&](auto&& self, int a, int b) -> int {      // persistent leftist heap merge
        if (!a || !b) return a ^ b;
        if (T[a].key > T[b].key) swap(a, b);
        T.push_back(T[a]); int c = sz(T) - 1;
        int r = self(self, T[c].r, b); T[c].r = r;
        if (T[T[c].l].rk < T[T[c].r].rk) swap(T[c].l, T[c].r);
        T[c].rk = T[T[c].r].rk + 1;
        return c;
    };
    vector<vector<int>> out(n); for (int i = 0; i < sz(E); i++) out[E[i][0]].push_back(i);
    vector<int> H(n, 0);
    for (int u : order) {                                       // next(u) is popped before u
        if (u != t) H[u] = H[E[tree[u]][1]];
        for (int e : out[u]) {
            int v = E[e][1]; if (e == tree[u] || d[v] >= INF) continue;
            T.push_back({E[e][2] + d[v] - d[u], v, 0, 0, 1}); int x = sz(T) - 1;
            H[u] = merge(merge, H[u], x);
        }
    }
    vector<ll> res{d[s]};
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
    if (H[s]) q.push({d[s] + T[H[s]].key, H[s]});
    while (sz(q) && sz(res) < k) {
        auto [c, x] = q.top(); q.pop(); res.push_back(c);
        for (int y : {T[x].l, T[x].r}) if (y) q.push({c - T[x].key + T[y].key, y});   // swap this sidetrack for a sibling
        if (int y = H[T[x].to]) q.push({c + T[y].key, y});                              // add one more sidetrack after it
    }
    return res;
}

(Library Checker “K-Shortest Walk”. Recursion in merge is $O(\log m)$ deep.) For $k=2$ specifically, don’t reach for this machinery: a forward Dijkstra, a reverse Dijkstra, and one scan over the edges for the best sidetrack gives the second shortest walk directly.

Proof sketch: walks $\leftrightarrow$ sidetrack sequences, and the enumeration

Given a walk from $s$ to $t$, mark its non-tree edges $e_1,\dots ,e_r$. Between consecutive sidetracks the walk follows tree edges, so $e_{i+1}$ leaves the tree path from $\text{head}(e_i)$ to $t$, i.e. $e_{i+1}\in H(\text{head}(e_i))$ (and $e_1\in H(s)$); conversely every such sequence is a walk. Its length telescopes to $d(s)+\sum \delta (e_i)$. The search treats each heap node as “the last sidetrack of the sequence”; from a sequence ending in node $x$ we either replace $x$ by one of its heap children (cost changes by the key difference, which is $\ge 0$ by heap order) or append the root of $H(\text{head}(x))$. Each sequence is reachable from the root by exactly one such chain (heap paths are unique), keys never decrease along the chain, so a best-first search pops sequences in nondecreasing cost. Each insertion into a persistent leftist heap copies $O(\log m)$ nodes, giving $O(m\log m)$ memory and preprocessing, and each output costs $O(\log k)$.

Yen: $k$ shortest simple paths

For the $j$-th path, for each spur position $i$ on the previous path: fix the root (first $i$ edges), forbid the next edge of every already-found path with the same root, forbid the root’s vertices, and find the shortest spur path to $t$. Candidates go into a set; the cheapest becomes the next path. Lawler’s modification (worth having): remember, per already-found path, the deviation index it was branched from, and only re-spur at positions at or after that index — this skips recomputing spurs that provably can’t produce anything new, a constant-factor speedup. On a DAG, $k$ shortest walks is simpler still: a DP keeping the best $k$ values at each vertex, no heap needed.

vector<pair<ll, vector<int>>> yen(int n, const vector<array<ll, 3>>& E, int s, int t, int K) {   // paths as edge-id lists
    const ll INF = LLONG_MAX / 4; vector<vector<int>> out(n);
    for (int i = 0; i < sz(E); i++) out[E[i][0]].push_back(i);
    auto sp = [&](int src, const vector<char>& banV, const vector<char>& banE) -> pair<ll, vector<int>> {
        vector<ll> d(n, INF); vector<int> pe(n, -1); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        d[src] = 0; pq.push({0, src});
        while (sz(pq)) {
            auto [du, u] = pq.top(); pq.pop(); if (du != d[u]) continue;
            for (int e : out[u]) { int v = E[e][1]; if (banE[e] || banV[v] || du + E[e][2] >= d[v]) continue; d[v] = du + E[e][2]; pe[v] = e; pq.push({d[v], v}); }
        }
        if (d[t] >= INF) return {INF, {}};
        vector<int> p; for (int v = t; v != src; v = E[pe[v]][0]) p.push_back(pe[v]);
        reverse(all(p)); return {d[t], p};
    };
    vector<pair<ll, vector<int>>> A; set<pair<ll, vector<int>>> B;
    vector<char> banV(n), banE(sz(E));
    auto first = sp(s, banV, banE); if (first.first >= INF) return A;
    if (s == t) return {{0, {}}};
    A.push_back(first);
    while (sz(A) < K) {
        const auto prev = A.back().second; ll rootCost = 0; int spur = s;
        for (int i = 0; i < sz(prev); i++) {
            vector<int> root(prev.begin(), prev.begin() + i);
            for (auto& [c, p] : A) if (sz(p) > i && equal(root.begin(), root.end(), p.begin())) banE[p[i]] = 1;
            for (int e : root) banV[E[e][0]] = 1;
            auto [c, spurPath] = sp(spur, banV, banE);
            if (c < INF) { auto full = root; full.insert(full.end(), all(spurPath)); B.insert({rootCost + c, full}); }
            fill(all(banV), 0); fill(all(banE), 0);
            rootCost += E[prev[i]][2]; spur = E[prev[i]][1];
        }
        if (B.empty()) break;
        A.push_back(*B.begin()); B.erase(B.begin());
    }
    return A;
}

Proof sketch: Yen finds the paths in order

Let $P$ be the $j$-th shortest simple path and let $Q$ be the found path that shares the longest common prefix with $P$, of length $i$. Then $P$ deviates from $Q$ at position $i$, and its first $i$ edges form the root used when $Q$‘s spur at $i$ was processed. At that moment, $P$‘s next edge was not forbidden (no found path with that root uses it, otherwise that path would share a longer prefix), and $P$‘s suffix avoids the root’s vertices (it is simple). So the spur search produced a candidate no longer than $P$, with the same root; candidates are simple paths distinct from all found ones. Hence the cheapest remaining candidate has cost exactly that of the $j$-th shortest simple path.

Disjoint paths

• $k$ edge-disjoint (vertex-disjoint after splitting) paths minimising total cost: min-cost flow of value $k$ with unit capacities (Min-Cost Flow). For $k=2$ this is Suurballe’s algorithm: Dijkstra, reweight by potentials, reverse the first path’s edges, Dijkstra again, cancel opposite edges. For general $k$, run $k$ rounds of successive shortest augmenting paths the same way (Suurballe–Tarjan), $O(k(m+n\log n))$ — the telecom motivation is a primary route plus backups that each survive a single node failure.
• Maximum number of disjoint paths: max flow with unit capacities; Menger’s theorem says it equals the minimum cut (Min Cut).
• Two vertex-disjoint paths between fixed pairs $(s_1,t_1),(s_2,t_2)$ in undirected graphs is polynomial but intricate (2-linkage); in directed graphs it is NP-hard.

Proof: why greedy deletion fails and flows work

Greedy: in a graph where the shortest path uses the “middle” edge of two otherwise disjoint routes, deleting it can disconnect $s$ from $t$ or force an expensive second path, while the optimal pair uses neither the shortest path’s prefix nor its suffix in the same combination. Flows: a set of $k$ edge-disjoint paths is exactly an integral flow of value $k$ with unit capacities (decompose the flow into paths; cycles of nonnegative cost can be dropped). Min-cost flow by successive shortest paths is optimal, and the second augmenting path may traverse reversed edges of the first, which is exactly the rerouting greedy can’t do.