Skip to content

k Shortest Paths

Prerequisite reading: Dijkstra's algorithm, the A* algorithm, persistent mergeable heaps

Problem statement

Given a directed graph with \(n\) vertices and \(m\) edges, find the length of the \(k\)-th shortest of all the distinct paths from \(s\) to \(t\).

The term 'path'

A "path" in this article may pass through the same edge or the same vertex more than once, so the strictly correct name is "walk", not "path". Strictly speaking, the problem discussed here is likewise the \(k\) shortest walks problem. Following common usage, however, this article keeps the name "path", and calls a path that does not intersect itself a "simple path".

A* algorithm

A* is a search algorithm. It gives every state \(x\) an evaluation function \(f(x)=g(x)+h(x)\), where \(g(x)\) is the actual cost of reaching \(x\) from the initial state and \(h(x)\) is the estimated cost of the best path from \(x\) to the goal state. At each step, the search takes the state \(x\) with the best \(f(x)\) and expands all its successor states. A priority queue can maintain these values.

For the \(k\) shortest paths problem, let \(h(x)\) be the length of the shortest path from the current vertex to the target vertex \(t\). Precompute it for every vertex by running a single-source shortest paths algorithm from \(t\) on the transpose graph. A state records two values, the vertex \(x\) it has reached and the distance \(g(x)\) traveled so far, and is written \((x,g(x))\). Start by pushing the initial state \((s,0)\) into the priority queue. At each step, pop the state with the smallest \(f(x)=g(x)+h(x)\), enumerate the outgoing edges of its vertex \(x\), and push the corresponding successor states. When a vertex is popped for the \(k\)-th time, the \(g(x)\) of that state is the length of the \(k\)-th shortest path from the start vertex \(s\) to that vertex.

This search can be optimized. We only need the \(k\)-th shortest path from the start vertex to the target vertex, so once a vertex has been popped \(k\) times, the states popped at that vertex later need not be expanded. They cannot affect the final answer: the first \(k\) pops of the vertex already produced \(k\) valid paths to it, which are enough to construct the \(k\) shortest paths to the target vertex.

Each vertex is expanded at most \(k\) times, so each edge adds a state to the priority queue at most \(k\) times. The algorithm therefore runs in \(O(km\log km)\) time and \(O(km)\) space. Compared with a plain search, A* adds pruning directed at the target vertex \(t\), but this improves only the constant factor, not the asymptotic complexity. The algorithm of this section is not fast, but within the same complexity it finds the \(k\) shortest paths from the start vertex \(s\) to every vertex (of the shortest path tree rooted at \(t\)).

Implementation

Reference implementation for the template problem Library Checker - K-Shortest Walk
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// 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 * m * log(k * m)).
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 solution

The algorithm above in fact finds the \(k\) shortest paths to every vertex. If all we want is the \(k\) shortest paths to a given target vertex \(t\), we can do better. This section presents an \(O(m\log m+k\log k)\) algorithm based on a persistent mergeable heap.

Shortest path tree and sidetrack edges

The bottleneck of the algorithm above is that the answer is updated only when the search reaches the target vertex \(t\). But two paths may differ very little. The second shortest path, for example, may differ from the shortest path only by a detour through one extra vertex in place of a single edge, with the rest of the path identical; yet the algorithm above may have to search all those shared edges again to find it. Only the detours matter, so to obtain the \(k\) shortest paths it is enough to consider the \(k\) cheapest ways of making detours. This leads to the notion of a shortest path tree.

Run a single-source shortest paths algorithm from the target vertex \(t\) on the transpose graph. For every vertex \(x\), record the length \(h(x)\) of the shortest path from \(x\) to \(t\), and the first edge \(f_x\) of a shortest path starting at \(x\); if several edges are optimal, take the one recorded when Dijkstra's algorithm relaxed \(x\). All the edges \(f_x\) and their endpoints form a tree, and the simple path in the tree from any vertex \(x\) to the root \(t\) is a shortest path from \(x\) to \(t\). This is the shortest path tree \(T\).

With the shortest path tree \(T\) in hand, we can compute how long a detour each edge outside \(T\) makes. For an edge \(e=(u,v)\notin T\) with edge weight \(w\), define a new edge, again from \(u\) to \(v\), with cost \(\Delta(e)=w + h(v) - h(u)\). This article calls these edges of weight \(\Delta(e)\) sidetrack edges, and the weight \(\Delta(e)\) the sidetrack cost. Since \(h(u)\le w+h(v)\), a sidetrack cost is never negative. An edge whose endpoints are not both in the shortest path tree \(T\) has no effect on the \(k\) shortest paths to \(t\) and can simply be deleted.

In the figure below, the directed graph \(G\) is on the left; on the right are its shortest path tree \(T\) (thick edges) and the corresponding sidetrack edges (thin edges):

Let \(P\) be the sequence of edges of a path from \(s\) to \(t\), and let \(P'\) be \(P\) with its intersection with \(T\) removed. List the edges of \(P'\) in order. Any two adjacent edges \(e_1=(u_1,v_1)\) and \(e_2=(u_2,v_2)\) then satisfy:

  • Condition \((*)\): the tail \(u_2\) of the later edge is an ancestor of the head \(v_1\) of the earlier edge in the shortest path tree \(T\) (possibly \(v_1\) itself). For the first edge of the sequence, take \(s\) as the "head of the earlier edge".

The reason is that in the original path \(P\), the vertices \(v_1\) and \(u_2\) are joined by some tree edges of \(T\). Conversely, an edge sequence \(P'\) that satisfies condition \((*)\) corresponds to exactly one path \(P\) in the graph \(G\), because the simple path between \(v_1\) and \(u_2\) in the shortest path tree \(T\) is unique. So the paths \(P\) in the original graph are in one-to-one correspondence with the sequences \(P'\) of sidetrack edges that satisfy condition \((*)\). Moreover, the length of \(P\) is the shortest path length \(h(s)\) plus the sum of these sidetrack costs:

\[ h(s)+\sum_{e\in P'}\Delta(e). \]

The task of finding the \(k\)-th shortest path therefore becomes that of finding the sequence \(P'\) of sidetrack edges that satisfies condition \((*)\) and has the \(k\)-th smallest cost.

To deal with condition \((*)\), do not search for ancestors in the shortest path tree at every query: pass each vertex's set of sidetrack edges down to its descendants in the tree instead. This amounts to building the following graph \(G'\):

In this graph, condition \((*)\) says that the edges of \(P'\) join head to tail, that is, \(P'\) is a path in the graph \(G'\). The problem becomes that of finding, in this graph, the \(k\)-th shortest path that starts at \(s\) and ends at any vertex. Unlike in the original \(k\) shortest paths problem, the path no longer has to end at the target vertex \(t\).

The transformed problem is easy to solve. Start from the start vertex \(s\) and expand paths in increasing order of length with a priority queue (the same vertex may be popped many times). Each time a vertex is popped from the priority queue, a path in \(G'\) has been found, and it corresponds to a path to the target vertex \(t\) in \(G\).

Optimization with a persistent mergeable heap

The idea of the algorithm is now clear, but a naive implementation is too slow. A single vertex of \(G'\) may have \(\Theta(m)\) edges, so each time a vertex is expanded, an edge set of size \(\Theta(m)\) may have to be pushed into the priority queue. In fact there is no need to push all the edges: in many cases, only the shortest of them can ever be popped later on. So the whole edge set of a vertex can be pushed into the priority queue as a single unit, as long as its shortest edge can be accessed quickly each time.

This suggests storing the edge set of each vertex in a min-heap. The priority queue then stores only these heaps, and the cost of a heap is the cost of the path that corresponds to the edge at the top of the heap. Whenever the front of the queue is popped, also pop the top edge from that heap. Then push the heap, with its top removed, back into the priority queue, and also push the heap of the sidetrack edge set at the head of the top edge.

Storing the edge sets in heaps also solves the problem of passing them down the shortest path tree. Passing an edge set down means merging the edge set of the current vertex into those of its children, so the heap must support merging. And the merge into a child must not destroy the edge set at the current vertex, so the heap must also be persistent. This is exactly a persistent mergeable heap.

The complete algorithm is as follows:

  1. Run a single-source shortest paths algorithm from the target vertex \(t\) to obtain the shortest path tree.
  2. For every vertex of the shortest path tree, build its set of sidetrack edges and store it in a persistent mergeable heap.
  3. Go down the edges of the shortest path tree from the target vertex \(t\) (in BFS order, say), merging the heap of every vertex into the heaps of its children.
  4. Record the shortest path length \(h(s)\) as the first answer. Then, starting from the start vertex \(s\), push the heap at \(s\) into the priority queue.
  5. Pop the heap at the front of the queue and record the answer. Push the heap, with its top removed, back into the priority queue, and push the heap at the head of the top edge.

The persistent mergeable heap is usually implemented as a leftist tree or a randomized heap. The last step can then be optimized further. Internally, these heaps are binary trees. After the top is popped, the left and right children would normally be merged and the merged heap pushed into the priority queue. In this algorithm the merge can be skipped: push the heaps rooted at the two children into the priority queue separately. This saves the \(O(\log m)\) cost of a merge. Each time the front heap is popped, at most three new heaps are pushed, so the priority queue has size \(O(k)\). A single query therefore takes only \(O(\log k)\) time, and the queries take \(O(k\log k)\) in total.

Building the shortest path tree and building the persistent mergeable heaps both take \(O(m\log m)\), so the whole algorithm runs in \(O(m\log m+k\log k)\) time.

Implementation

Reference implementation for the template problem Library Checker - K-Shortest Walk
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
// Submission: https://judge.yosupo.jp/submission/311623
#include <algorithm>
#include <ctime>
#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;
}

Practice problems

References and notes