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)][0]
    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)][0]
    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[0][0]+w[(n,v)],npaths[0][1]+[n]))
                npaths = npaths[1:]
            vpaths.sort()
            newpaths = []
            while vpaths[-1][0] > npaths[0][0] + w[(n,v)]:
                # Found shorter path to v via n
                newpaths.append((npaths[0][0]+w[(n,v)],npaths[0][1]+[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},
}