k-th Shortest Path

Prerequisites: Dijkstra's algorithm, A* algorithm, and persistent mergeable heaps

Problem statement

Given a directed graph with $n$ vertices and $m$ edges, find among all distinct paths from $s$ to $t$ the path of length rank $k$.

A* algorithm

A* is a search algorithm. It assigns each current state $x$ an evaluation function $f(x)=g(x)+h(x)$, where $g(x)$ is the actual cost from the initial state to the current state and $h(x)$ is the estimated cost of the best path from the current state to the target state. During the search, it repeatedly extracts the state with the best $f(x)$ and expands all successor states of that state $x$. A priority queue can maintain these values.

When solving the $k$-shortest-path problem, let $h(x)$ be the shortest-path length from the current vertex to the destination $t$. Run single-source shortest path from $t$ on the reversed graph to precompute this value for every vertex. Each state records two values: the current vertex $x$ and the distance $g(x)$ already traveled; denote such a state by $(x,g(x))$. Initially, insert $(s,0)$ into the priority queue. Each time, extract a state with minimum evaluation value $f(x)=g(x)+h(x)$, enumerate all outgoing edges of its vertex $x$, and insert the corresponding successor states into the priority queue. When a vertex is visited for the $k$-th time, the corresponding state's $g(x)$ is the length of the path from the starting vertex $s$ with rank $k$.

This search can be optimized. Since we only need the $k$-th shortest path from the initial vertex to the target, once states reaching a vertex have been extracted more than $k$ times, we need not expand their successors. Such a state cannot affect the final answer: the previous $k$ extractions of that vertex have already produced $k$ valid paths to it, enough to construct the $k$ shortest paths to the target.

With a priority-queue-optimized Dijkstra algorithm, all edges can be inserted into the priority queue at most $k$ times, so the time complexity is $O(km\log km)$ and the space complexity is $O(km)$. Compared with direct search, A* prunes with respect to the target vertex $t$, but this improves only the constant factor, not the asymptotic complexity. Although the algorithm described here does not have an excellent complexity, within the same complexity it can find from the starting vertex $s$ to every vertex in the shortest-path tree rooted at $t$ the first $k$ shortest paths.

Implementation

// Submission: https://judge.yosupo.jp/submission/311622
#include <iostream>
#include <queue>
#include <vector>

constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

struct Edge {
  int u, v, c;

  Edge(int u, int v, int c) : u(u), v(v), c(c) {}
};

int n, m, s, t, k;
std::vector<std::vector<int>> gr, ig;  // Graph and inverse graph.
std::vector<Edge> edges;               // Edges.
std::priority_queue<std::pair<long long, int>,
                    std::vector<std::pair<long long, int>>, std::greater<>>
    pq;

std::vector<long long> dist_t;

// Calculate distances to the destination node t. (Dijkstra)
void calc_distances_to_t() {
  dist_t.assign(n, inf);
  dist_t[t] = 0;
  pq.emplace(dist_t[t], t);
  while (!pq.empty()) {
    long long di = pq.top().first;
    int cur = pq.top().second;
    pq.pop();
    if (di > dist_t[cur]) continue;
    for (auto e : ig[cur]) {
      int nxt = edges[e].u;
      auto di_nxt = di + edges[e].c;
      if (di_nxt < dist_t[nxt]) {
        dist_t[nxt] = di_nxt;
        pq.emplace(di_nxt, nxt);
      }
    }
  }
}

std::vector<long long> ans;

// Find the k shortest walk. (A* search)
// Complexity: O(k * n * log(k * n)).
void find_k_shortest_walks() {
  ans.assign(k, -1);
  std::vector<int> cnt(n);
  pq.emplace(dist_t[s], s);
  while (!pq.empty()) {
    long long cost = pq.top().first;
    int cur = pq.top().second;
    pq.pop();
    // Skip unreachable nodes.
    if (cost >= inf) continue;
    if (cur == t) ans[cnt[t]] = cost;
    ++cnt[cur];
    // Terminate when the destination has been visited k times.
    if (cnt[t] >= k) break;
    // Expand the same node at most k times.
    if (cnt[cur] > k) continue;
    for (auto e : gr[cur]) {
      int nxt = edges[e].v;
      auto cost_nxt = cost - dist_t[cur] + edges[e].c + dist_t[nxt];
      pq.emplace(cost_nxt, nxt);
    }
  }
}

int main() {
  // Input.
  std::cin >> n >> m >> s >> t >> k;
  gr.resize(n);
  ig.resize(n);
  edges.reserve(m);
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    std::cin >> u >> v >> c;
    edges.emplace_back(u, v, c);
    gr[u].push_back(i);
    ig[v].push_back(i);
  }
  // Calculate.
  calc_distances_to_t();
  find_k_shortest_walks();
  // Output.
  for (auto x : ans) std::cout << x << '\n';
  return 0;
}

Persistent mergeable-heap approach

The preceding algorithm actually finds the $k$ shortest paths to every vertex. If we only want the shortest paths to a given target $t$, specifically the $k$ shortest paths to it, this can be done faster. This section presents an $O(m\log m+k\log k)$ approach based on persistent mergeable heaps.

Shortest-path tree and sidetracks

The bottleneck of the preceding algorithm is that it updates the answer only when it reaches the target vertex $t$. Yet different paths may differ very little. For example, a second-shortest path may differ from the shortest path only by taking one extra detour at a single edge, while all other parts are identical; the preceding algorithm may nevertheless have to search those identical edges again before finding the second-shortest path. Since only the detour matters, to obtain the $k$ shortest paths we need only consider the $k$ cheapest detour patterns. This leads to the concept of a shortest-path tree.

Starting from the target $t$, run single-source shortest path on the reversed graph; for each vertex $x$, record its shortest-path length to $t$, denoted $h(x)$, and for that vertex $x$, record the first edge $f_x$ on a shortest path; if there are multiple optimal choices, any one will do. All these edges $f_x$ and their endpoints form a tree, and the simple path from every vertex $x$ in the tree to the root $t$ is a shortest path from $x$ to $t$. This is the shortest-path tree $T$.

After obtaining the shortest-path tree $T$, we can compute how much extra cost each edge not in $T$ incurs. For an edge $e=(u,v)\notin T$ with weight $w$, define a new edge still directed from $u$ to $v$, with cost $\Delta(e)=w + h(v) - h(u)$. We call edges with weight $\Delta(e)$ sidetracks, and call $\Delta(e)$ the sidetrack cost. If an edge does not have both endpoints in the shortest-path tree $T$, it cannot affect the computation at target $t$ of the $k$ shortest paths, so it can be deleted directly.

The left side of the figure below is a directed graph $G$; the right side is its shortest-path tree $T$ (thick edges) and corresponding sidetracks (thin edges):

For a path from $s$ to $t$, let its traversed edge set be $P$; remove from $P$ its intersection with $T$ to obtain $P'$. When the edges in $P'$ are listed in order, every adjacent pair $e_1=(u_1,v_1)$ and $e_2=(u_2,v_2)$ satisfies

• Condition $(*)$: the start $u_2$ of the latter is an ancestor of the end $v_1$ of the former in the shortest-path tree $T$ (including the endpoint itself).

This is because the original path $P$ connects $v_1$ and $u_2$ by several tree edges from $T$. Conversely, for an edge set satisfying condition $(*)$, namely a sidetrack set $P'$, there is a unique path in graph $G$, namely $P$, corresponding to it, because the simple path between $v_1$ and $u_2$ in the shortest-path tree $T$ is unique. Thus every path $P$ in the original graph corresponds bijectively to a sequence satisfying condition $(*)$ of sidetracks $P'$. Moreover, the length of path $P$ equals the shortest-path length $h(s)$ plus the sum of the sidetrack costs:

These observations transform the task of finding the $k$ shortest paths into finding the $k$-th cheapest sequence satisfying condition $(*)$, namely a sidetrack sequence $P'$.

To handle condition $(*)$, instead of searching for ancestors in the shortest-path tree at every query, propagate each vertex's set of sidetracks to its descendants in the tree. This is equivalent to constructing the following graph $G'$:

In this graph, condition $(*)$ becomes the requirement that consecutive sidetracks in $P'$ connect end to end; in other words, $P'$ is a path in graph $G'$. The problem is further transformed into finding a path starting from $s$ whose length is the $k$-th smallest and that reaches any vertex. Unlike the original $k$-shortest-path problem, the path no longer needs to end at the target vertex $t$.

The transformed problem is easy to solve. Start at $s$ and run single-source shortest path. Each time a vertex is extracted from the priority queue, we have found a path in graph $G'$, which corresponds to a path in graph $G$ reaching the target vertex $t$.

Persistent mergeable-heap optimization

The algorithmic idea is now clear, but a naive implementation is too expensive. In graph $G'$, the number of edges incident to a single vertex may be $\Theta(m)$, so each single-source shortest-path computation may need to push an edge set of size $\Theta(m)$ into the priority queue. In fact, it is unnecessary to push all edges: often, only the smallest of the queued edges can be popped later. We can therefore treat the entire edge set at a vertex as one stored object and push it into the priority queue, as long as we can access its minimum edge quickly.

This suggests using a min-heap to store the edge set at each vertex. The single-source shortest-path priority queue needs to store only these heaps, with each heap's cost equal to the shortest-path cost represented by its top element. Each time the queue head is popped, the top edge must also be popped from the heap at the head. The heap after removing its top must be pushed back into the priority queue, and the heap corresponding to the sidetrack set at the popped edge's endpoint must also be pushed into the priority queue.

Using heaps to store edge sets also solves the problem of propagating edge sets down the shortest-path tree. Propagating a set means merging the current vertex's edge set into its child, so the heap must support merging. At the same time, the current vertex's edge set must not be destroyed, so the heap must also be persistent. This is exactly a persistent mergeable heap.

This gives the complete algorithm:

1. Start from the target vertex $t$, run single-source shortest path, and find the shortest-path tree.
2. Build the sidetrack set for every vertex in the shortest-path tree and store it in a persistent mergeable heap.
3. Along the edges of the shortest-path tree, start from the target vertex $t$ and merge each vertex's heap into the heaps of its children.
4. Start from the initial vertex $s$ and push its heap into the priority queue.
5. Pop the heap at the head of the queue and record the answer; then push the heap after removing its top back into the priority queue, and push the heap at the endpoint of the top edge into the priority queue.

A leftist tree or randomized heap is generally used to implement a persistent mergeable heap. The last step can be optimized further. These heaps are binary trees. After popping the top, one would normally merge the two child heaps and push the resulting heap's top into the priority queue. In this algorithm, however, we can skip the merge and push the heaps corresponding to the two child nodes into the priority queue separately. This eliminates the $O(\log m)$ cost of one merge. Since at most three new heaps are pushed after each head heap is popped, the priority queue has size $O(k)$. Thus the time complexity of one query is reduced to $O(\log k)$, and the total query complexity is $O(k\log k)$.

Since both constructing the shortest-path tree and constructing the persistent mergeable heap take $O(m\log m)$ time, the total time complexity is $O(m\log m+k\log k)$.

Implementation

// Submission: https://judge.yosupo.jp/submission/311623
#include <algorithm>
#include <iostream>
#include <queue>
#include <random>
#include <vector>

std::mt19937_64 rng(static_cast<std::mt19937_64::result_type>(time(nullptr)));

constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

// Persistent Randomized Heap.
struct PersistentRandomizedHeap {
  static constexpr int N = 1e7;
  int id;
  std::vector<int> rt, lc, rc, to;
  std::vector<long long> va;

  int new_node(long long cost, int _to) {
    ++id;
    va[id] = cost;
    to[id] = _to;
    return id;
  }

  int copy_node(int x) {
    ++id;
    lc[id] = lc[x];
    rc[id] = rc[x];
    va[id] = va[x];
    to[id] = to[x];
    return id;
  }

  int meld(int x, int y, std::mt19937_64::result_type rand) {
    if (!x || !y) return x | y;
    if (va[x] > va[y]) std::swap(x, y);
    x = copy_node(x);
    if (rand & 1) std::swap(lc[x], rc[x]);
    rc[x] = meld(rc[x], y, rand >> 1);
    return x;
  }

  PersistentRandomizedHeap() : id(0), rt(N), lc(N), rc(N), to(N), va(N) {}

  void insert(int i, long long cost, int _to) {
    rt[i] = meld(rt[i], new_node(cost, _to), rng());
  }

  void merge(int i, int j) { rt[i] = meld(rt[i], rt[j], rng()); }

} heaps;

struct Edge {
  int u, v, c;

  Edge(int u, int v, int c) : u(u), v(v), c(c) {}
};

int n, m, s, t, k;
std::vector<std::vector<int>> gr, ig;
std::vector<Edge> edges;
std::priority_queue<std::pair<long long, int>,
                    std::vector<std::pair<long long, int>>, std::greater<>>
    pq;

std::vector<long long> dist_t;
std::vector<int> out;

// Calculate distances to the destination node t. (Dijkstra)
// Record the optimal outgoing edges which form the shortest path tree T.
void calc_distances_to_t() {
  dist_t.assign(n, inf);
  dist_t[t] = 0;
  out.assign(n, -1);
  pq.emplace(dist_t[t], t);
  while (!pq.empty()) {
    long long di = pq.top().first;
    int cur = pq.top().second;
    pq.pop();
    if (di > dist_t[cur]) continue;
    for (auto e : ig[cur]) {
      int nxt = edges[e].u;
      auto di_nxt = di + edges[e].c;
      if (di_nxt < dist_t[nxt]) {
        dist_t[nxt] = di_nxt;
        out[nxt] = e;
        pq.emplace(di_nxt, nxt);
      }
    }
  }
}

// Construct sidetracks and propagate them through tree T.
void build_sidetracks() {
  // Insert all valid sidetracks into heaps.
  for (int i = 0; i < m; ++i) {
    auto edge = edges[i];
    if (out[edge.u] != i && dist_t[edge.u] < inf && dist_t[edge.v] < inf) {
      heaps.insert(edge.u, edge.c + dist_t[edge.v] - dist_t[edge.u], edge.v);
    }
  }
  // Propagate sidetracks down the shortest path tree.
  std::queue<int> q;
  q.push(t);
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();
    for (auto e : ig[cur]) {
      auto nxt = edges[e].u;
      if (out[nxt] == e) {
        heaps.merge(nxt, cur);
        q.push(nxt);
      }
    }
  }
}

std::vector<long long> ans;

// Insert a non-empty heap into the priority queue.
// Total cost is the heap top value adjusted by accumulated cost.
void insert(int x, long long cost) {
  if (x) pq.emplace(cost + heaps.va[x], x);
}

// Find the k shortest paths in the sidetrack graph. (Dijkstra)
// These correspond to the k shortest walks in the original graph.
void find_k_shortest_walks() {
  int cnt = 0;
  ans.assign(k, -1);
  if (dist_t[s] >= inf) return;
  ans[cnt++] = dist_t[s];
  insert(heaps.rt[s], dist_t[s]);
  while (!pq.empty() && cnt < k) {
    auto cost = pq.top().first;
    int cur = pq.top().second;
    pq.pop();
    ans[cnt++] = cost;
    insert(heaps.lc[cur], cost - heaps.va[cur]);
    insert(heaps.rc[cur], cost - heaps.va[cur]);
    insert(heaps.rt[heaps.to[cur]], cost);
  }
}

int main() {
  // Input.
  std::cin >> n >> m >> s >> t >> k;
  gr.resize(n);
  ig.resize(n);
  edges.reserve(m);
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    std::cin >> u >> v >> c;
    edges.emplace_back(u, v, c);
    gr[u].push_back(i);
    ig[v].push_back(i);
  }
  // Calculate.
  calc_distances_to_t();
  build_sidetracks();
  find_k_shortest_walks();
  // Output.
  for (auto x : ans) std::cout << x << '\n';
  return 0;
}

Exercises

• 「SDOI2010」Magic Pig Academy

References and notes

• [Tutorial] k shortest paths and Eppstein's algorithm by meooow - Codeforces