That is, to find 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 :

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 shortest path is to extend the Dijkstra’s algorithm. Instead of keeping the best route to a node, we keep the best 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

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 paths between nodes and by and the shortest edges between nodes and by . The idea is to find the paths between and by checking if is shorter.

We first define for two -vectors and that

  • as the minimum entries of
  • as the minimum entries of the union of and

and assume that the set of nodes is in an order so that we can establish the relationship for . Then the double sweep algorithm is formulated as follows:

  • Define to be a -vector of shortest edges’ length between and . If there are less than edges, set the corresponding values to infinity
  • Initialize for all as a -vector of infinities, except to denote the shortest path from to itself is zero.
  • Backward sweep: For in the reverse order of , compute for all
  • Forward sweep: For in the forward order of , compute for all
  • 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 . Define this shortest path tree as . For all the edges not in are called sidetrack edges, denote their set by .

Then a path between nodes and 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 . By computing the additional cost incurred by traversing a sidetracked edge, we can find the shortest paths by looking for valid subsets of 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},
}