Hello, Codeforces!

This is a blog on the $$$k$$$ shortest paths problem, and a neat algorithm by David Eppstein that can solve it very fast. You can find the original paper "Finding the $$$k$$$ Shortest Paths" here.

Given an edge-weighted directed graph $$$G$$$, the problem asks us to find the lengths of the $$$k$$$ shortest paths from a fixed vertex $$$s$$$ to a fixed vertex $$$t$$$.

This a very specific problem, and unlikely to show up in any programming contest. However, the ideas used to solve this may be useful in solving other problems.

Getting started

Prerequisites:

• Dijkstra's algorithm
• Persistent heaps

Let's get some things out of the way.

• The input graph is $$$G$$$, with $$$n$$$ vertices and $$$m$$$ edges. We assume $$$n \leq m$$$ to simplify some time complexities. We want to handle large $$$k$$$, in the same order as $$$m$$$.
• In each shortest path, it is allowed go over edges and through vertices more than once. It might be more accurate to call this a walk instead, but let's stick with path.
• Multiple edges, cycles and loops are allowed. Negative edge weights are not allowed.
• For simplicity, we assume $$$k$$$ paths always exist. If they don't it is easy to stop our algorithm early.
• $$$u$$$ and $$$v$$$ are labels used for vertices, $$$w$$$ is used for edge weights. $$$(u, v, w)$$$ denotes an edge from $$$u$$$ to $$$v$$$ with weight $$$w$$$. A dot denotes some part we don't care about, for example $$$(u, \cdot, \cdot)$$$ is just some outgoing edge from $$$u$$$.

Algorithm 1

Let's define a path that starts at $$$s$$$ and ends at $$$t$$$ as an $$$s–t$$$ path. We can modify Dijkstra's algorithm to find $$$k$$$ shortest $$$s–t$$$ paths.

q = empty min heap
count = 0-filled array
push (0, s) on q
while count[t] < k:
    (l, u) = pop q
    if count[u] == k:
        continue
    count[u] += 1
    if u == t:
        found a path of length l
    for each outgoing edge (u, v, w) from u:
        push (l + w, v) on q

Dijkstra's algorithm is usually implemented with adjacency lists and a binary heap in $$$O(m \log m)$$$. This modified version visits each vertex at most $$$k$$$ times, so it runs in $$$O(km \log km)$$$.

This is pretty good for small values of $$$k$$$, and you can solve Flight Routes on CSES using this method.

But can we do better? In the main loop, every time we pop something from the priority queue, we get a full path only when $$$u = t$$$.

Wouldn't it be great if every time we popped something .. it was sure to be a full path .. aha ha, just kidding.. unless? 😳

Algorithm 2

To simplify things, let's remove every vertex from $$$G$$$ from which we cannot reach $$$t$$$. Consider that we are at vertex $$$u$$$ and want to reach $$$t$$$. There is one optimal edge $$$nxt_u = (u, p_u, \cdot)$$$ which goes out from $$$u$$$ and is on a shortest path to $$$t$$$. If there is more than one such edge, we can pick one arbitrarily. Now, if instead of taking $$$nxt_u$$$ we go along some other edge $$$(u, v, w)$$$, how much more does it cost us compared to the shortest path? Let's name this cost $$$sidetrack(u, v, w)$$$. If $$$d_u$$$ is the length of the shortest path from $$$u$$$ to $$$t$$$, then

At $$$v$$$, we can once again continue on the shortest path, or get sidetracked by another edge. And so on until we reach $$$t$$$.
In fact, any path that ends at $$$t$$$ can be completely described by the starting vertex and the sequence of sidetrack edges in the path. This is because the rest of the edges in the path are $$$nxt$$$ edges and there is no ambiguity.

Fig 1. An example graph with $$$d$$$ values and the same graph with sidetrack costs.

So, consider a graph $$$G'$$$ where there are only sidetrack edges. In this graph, for every edge $$$(u, v, w)$$$, except for $$$nxt_u$$$, we keep an edge $$$(u, v, sidetrack(u, v, w))$$$. In other words, we keep sidetrack edges but with sidetrack costs instead of the original costs. We don't keep $$$nxt_u = (u, p_u, \cdot)$$$ because it continues the shortest path. Additionally, we consider all sidetrack edges out of $$$p_u$$$, $$$p_{p_u}$$$, ..., $$$t$$$ to be directly connected to $$$u$$$.

Let's define an $$$s$$$ path to be a path that starts at $$$s$$$. There is no restriction on which vertex it ends on.

For any vertex $$$s$$$, there is a bijection between $$$s–t$$$ paths in $$$G$$$ and $$$s$$$ paths in $$$G'$$$. A path in $$$G$$$ corresponds to the path in $$$G'$$$ with the same sequence of sidetrack edges. The length of a path in $$$G$$$ is $$$d_s$$$ plus the length of the corresponding path in $$$G'$$$.

Fig 2. $$$G'$$$ obtained from the example graph

If we find the $$$k$$$ shortest $$$s$$$ paths in $$$G'$$$, we also find the $$$k$$$ shortest $$$s–t$$$ paths in $$$G$$$. We can do that using a Dijkstra-like algorithm where we pop from the heap $$$k$$$ times. Let's call it the $$$k$$$-pop algorithm.

q = empty min heap
push (d[s], s) on q
repeat k times:
    (l, u) = pop q
    found a path of length l
    for each outgoing edge (u, v, w) from u:
        push (l + w, v) on q

Our complete algorithm takes 3 steps.

1. Calculating $$$d_u$$$ and $$$nxt_u$$$
   $$$d_u$$$ and $$$nxt_u$$$ for all vertices $$$u$$$ can be calculated in one run of Dijkstra's algorithm on $$$G$$$ with its edges flipped with $$$t$$$ as source. This takes $$$O(m \log m)$$$.
2. Construction of $$$G'$$$
   We use the usual adjacency list representation. If $$$adj_{p_u}$$$ is the list of sidetrack edges out of $$$p_u$$$, $$$p_{p_u}$$$, ..., $$$t$$$, we only need to add the sidetrack edges out of $$$u$$$ to $$$adj_{p_u}$$$ to get $$$adj_u$$$, but we must not destroy $$$adj_{p_u}$$$. This is possible using a persistent structure. A singly linked list can be used, taking $$$O(1)$$$ per insertion. So, construction takes $$$O(m)$$$.
3. $$$k$$$-pop
   When $$$k$$$-popping, at every step we need to go over and push all outgoing edges from $$$u$$$ into the heap. There can be $$$O(m)$$$ such edges. So it takes $$$O(km \log km)$$$ to pop $$$k$$$ values off the heap.

Fig 3. Implementation of $$$G'$$$ using linked lists. Dashed lines connect linked list nodes.

The total time is $$$O(km \log km)$$$ 🤔
"Hey, I've seen this one!"
"What do you mean you've seen this? It's brand new."

Algorithm 3

The problem with $$$G'$$$ is that it is unbounded, there can be any number of edges out of a vertex. If $$$G'$$$ were a bounded graph with at most $$$c$$$ edges out a vertex, $$$k$$$-pop would take $$$O(kc \log kc)$$$ time instead.

Consider $$$adj_u$$$, which is a just a list right now. Can we avoid having to go on every edge from $$$u$$$? The only thing we do with the edges is add them to a min heap.

Let's make two changes to make $$$G'$$$ a bounded graph, and we'll call the new graph $$$G^{\prime\prime}$$$:

1. We make $$$adj_u$$$ into a min heap too! $$$adj_u$$$ will be a heap of sidetrack edges ordered by their sidetrack costs. By min heap, we mean here any tree where the key at a vertex is not greater than the key at any descendant vertex. And we want this tree to be bounded.
2. We incorporate $$$adj_u$$$ into $$$G^{\prime\prime}$$$. Every vertex in $$$adj_u$$$, which represents a sidetrack edge, becomes a vertex in $$$G^{\prime\prime}$$$.

So, for $$$adj_u$$$ we want

• a min heap
• that has bounded degree
• into which items can be inserted persistently

A candidate that fits our requirements is the leftist heap, which is also nice and easy to implement.

This transformation of $$$adj_u$$$ to a heap and inclusion into $$$G^{\prime\prime}$$$ does not affect the $$$k$$$-pop algorithm in the next step. It works correctly as before to give us the $$$k$$$ shortest $$$s–t$$$ paths in $$$G$$$.

This is because

• Every $$$s$$$ path in $$$G^{\prime\prime}$$$ corresponds to a $$$s–t$$$ path in $$$G$$$ as before. The sequence of the last sidetrack edges we go through in every heap we visit represents the path in $$$G$$$.
• We made $$$adj_u$$$ a min heap so that we use shorter sidetrack edges before longer ones. In other words, we only travel non-negative distances on $$$G^{\prime\prime}$$$, otherwise $$$k$$$-pop would fail.

For a vertex $$$u$$$, $$$adj_u$$$ points to the root of its heap of sidetrack edges. Every vertex in the heap, which represents some sidetrack edge $$$(u, v, \cdot)$$$, has 1 edge going to the heap of sidetrack edges of $$$v$$$, and at most 2 edges going to heap subtrees, since a leftist heap is a binary tree. So, every vertex in $$$G^{\prime\prime}$$$ has outdegree of at most 3.

Revisiting the full implementation,

1. Finding $$$d_u$$$ and $$$nxt_u$$$ still takes $$$O(m \log m)$$$.
2. Constructing the graph $$$G^{\prime\prime}$$$ now takes $$$O(m \log m)$$$, because there are $$$O(m)$$$ elements in the heap and insertion takes logarithmic time.
3. $$$k$$$-pop takes $$$O(k \log k)$$$ time.

Everything now runs in $$$O(m \log m + k \log k)$$$!

Fig 4. $$$G^{\prime\prime}$$$ obtained from the example graph. Dashed lines are heap connections.
The sharing of nodes due to persistence is not shown, because it becomes a complete mess.

This is close to, but not exactly the same as, Eppstein's algorithm. There is no mention of this algorithm in his paper, and I'm unaware of any existing name for it, so let's call it the simple version of Eppstein's algorithm. With this you can solve the following problems:

• K-Shortest Walk on Library Checker
• Shortest paths in the acmsguru problemset

Algorithm 4

We will try to optimize the construction of $$$G^{\prime\prime}$$$, which takes $$$O(m \log m)$$$ in the simple version. We'll build a slightly different graph to serve the same purpose, let's call it $$$G^{\prime\prime\prime}$$$.

$$$adj_u$$$ is a heap into which we added all sidetrack edges, giving it a size of $$$O(m)$$$. Let's instead add at most one edge for each vertex $$$u$$$, which is the sidetrack edge out of it with minimum cost (if it exists). We can form the rest of the sidetrack edges out of $$$u$$$ into another heap and attach it to the minimum cost edge. $$$adj_u$$$ now has size $$$O(n)$$$, and we can heapify elements in linear time, so the construction of $$$G^{\prime\prime\prime}$$$ takes $$$O(m + n \log n)$$$. There may be at most 4 edges out of a vertex in $$$G^{\prime\prime\prime}$$$.

This is Eppstein's algorithm proper, with the construction of $$$G^{\prime\prime\prime}$$$ running in $$$O(m + n \log n)$$$. The implementation is a little more complex compared to the simple version, and I did not find it to be reliably faster. Although I did not try too hard because the simple version is fast enough.

Implementation

Links to my submissions (using the simple version) on Library Checker:

• Haskell
• Python

Loose ends

Recovering a path: We have only discussed lengths of paths, but the paths themselves can also be recovered. During $$$k$$$-pop, we can keep track of the sidetrack edges we follow, the sequence of which completely determines the path in $$$G$$$.

Negative edge weights: For a graph with negative edge weights Dijkstra's algorithm cannot be used to calculate $$$d_u$$$ and $$$nxt_u$$$, but we can use other shortest path algorithms such as Bellman-Ford. The construction of $$$G^{\prime\prime}$$$ depends only on this, so everything after that is not affected. Of course, this sets back the total time complexity.

Data structure alternative: Using a heap isn't the only way to make $$$G'$$$ bounded. An alternative could be a sorted sequence, which can be implemented as a balanced binary search tree with the same time complexity of insertion. $$$k$$$-pop would then take $$$O(k \log k + k \log m)$$$, assuming getting the next element in the sequence takes $$$O(\log m)$$$. This will probably not be faster than a heap.

Moar optimization: Eppstein optimizes the algorithm (excluding the first Dijkstra) to a theoretical runtime of $$$O(n + m + k)$$$. I don't think this will be fast in practice, but you can check out the original paper for details. The link is at the top in case you missed it.

Wrapping up

That's it for this blog. Thanks to pajenegod for suggesting many corrections and improvements.

If you have any questions or comments, please leave them below.

I'll leave you with a bonus figure

Fig 5. A kitten