That is, to find $k$ paths between a pair of nodes in a graph that are the shortest.

This was asked in StackOverflow. And a couple different algorithms are available.

## Dijkstra’s Algorithm

Standard Dijkstra’s Algorithm is to find the shortest path, in $O(\vert V\vert^2)$:

Graph = G(V,E)      # The graph
tovisit = [s]       # open nodes: To examine
closed = []         # closed nodes: Examined
distance = {s:0}    # distance to a node
previous = {}       # previous node to yield best distance
while len(tovisit):
n = [v for v in tovisit if distance[v]==min(distance[v] for v in tovisit)]
neighbours = [v for v in V if (n,v) in E]
for v in neighbours:
try:
if distance[v] > distance[n]+w[(n,v)]:
distance[v] = distance[n] + w[(n,v)]
previous[v] = n
except KeyError:
distance[v] = distance[n]+w[(n,v)]
previous[v] = n
if v not in tovisit and v not in closed:
tovisit.push(v)
closed.append(n)


## Modified Dijkstra’s Algorithm

A trivial way to find the $k$ shortest path is to extend the Dijkstra’s algorithm. Instead of keeping the best route to a node, we keep the best $k$ routes to it, as illustrated follows:

# Modified Dijkstra's
Graph = G(V,E)          # The graph
tovisit = [s]           # open nodes: To examine
closed = []             # closed nodes: Examined
distance = {s:[(0,[])]} # distance to a node and the corresponding path
while len(tovisit):
n = [v for v in tovisit if min(distance[v])==min(min(distance[v]) for v in tovisit)]
neighbours = [v for v in V if (n,v) in E]
for v in neighbours:
try:
vpaths = distance[v]
npaths = sorted(distance[n])
while len(vpaths) < k:
# New path to v via n: We do not have k paths to v yet
vpaths.append((npaths+w[(n,v)],npaths+[n]))
npaths = npaths[1:]
vpaths.sort()
newpaths = []
while vpaths[-1] > npaths + w[(n,v)]:
# Found shorter path to v via n
newpaths.append((npaths+w[(n,v)],npaths+[n]))
npaths = npaths[1:]
vpaths = vpaths[0:-1]
if len(vpaths) == 0 or len(npaths) == 0: break
# update distance[v] with new paths and distances
vpaths.expand(newpaths)
distance[v] = vpaths
except KeyError:
# first encounter with node v
distance[v] = [(d+w[(n,v)],p+[n]) for d,p in distance[n]]
if v not in tovisit and v not in closed:
tovisit.append(v)
closed.append(n)


This algorithm is in $O(k\vert V\vert^2)$

## Double Sweep Algorithm

Double sweep algorithm is mentioned in the following papers:

It can work on a graph with parallel edges as long as no negative circuits. Denote the $k$ paths between nodes $x$ and $y$ by $D_{xy}$ and the $k$ shortest edges between nodes $x$ and $b$ by $d_{xy}$. The idea is to find the $k$ paths between $s$ and $t$ by checking if $D_{su}+d_{ut}$ is shorter.

We first define for two $k$-vectors $A$ and $B$ that

• $A+B$ as the minimum $k$ entries of ${a+b: a \in A, b \in B}$
• $\min(A,B)$ as the minimum $k$ entries of the union of $A$ and $B$

and assume that the set of nodes $V$ is in an order so that we can establish the relationship $u\le v$ for $u,v\in V$. Then the double sweep algorithm is formulated as follows:

• Define $d_{u,v}$ to be a $k$-vector of shortest edges’ length between $u$ and $v$. If there are less than $k$ edges, set the corresponding values to infinity
• Initialize $D_{sv}$ for all $v\in V$ as a $k$-vector of infinities, except $D_{ss} = (0,\infty,\infty,...)$ to denote the shortest path from $s$ to itself is zero.
• Backward sweep: For $v$ in the reverse order of $V$, compute $D_{sv}=\min(D_{su}+d_{uv}, D_{sv})$ for all $u\le v$
• Forward sweep: For $v$ in the forward order of $V$, compute $D_{sv}=\min(D_{su}+d_{uv}, D_{sv})$ for all $u\ge v$
• Repeat the backward and forward sweeps until we found no improvement is made

## Eppstein’s Algorithm

A neat algorithm developed by David Eppstein in his paper. It assume a digraph and find a shortest path tree from any node to node $t$. Define this shortest path tree as $T$. For all the edges not in $T$ are called sidetrack edges, denote their set by $G$.

Then a path between nodes $s$ and $t$ can be expressed implicitly by the set of sidetrack edges used. For example, an empty set represents the shortest path according to the shortest path tree $T$. By computing the additional cost incurred by traversing a sidetracked edge, we can find the $k$ shortest paths by looking for $k$ valid subsets of $G$ of minimum total cost.

@article{
title = {Iterative Methods for Determining the k Shortest Paths in a Network},
author = {D. R. Shier},
journal = {Networks},
volume = 6,
pages = {205--230},
year = 1974,
}
@article{
title = {Computational Experience with an Algorithm for Finding the k Shortest Paths in a Network},
author = {D. R. Shier},
journal = {J. Res. Natl. Bur. Std.},
volume = 78B,
pages = {139--165},
month = {July-September},
year = 1974,
}
@book{
title = {Optimization Algorithms for Networks and Graphs},
author = {Edward Minieka},
publisher = {Marcel Dekker},
address = {New York NY},
year = 1978,
isbn = {0-8247-6642-3},
callnumber = {QA166.M56},
}