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},