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