Path me and I'll path you!

The shortest path problem is one of the most important problems in OR. We shall examine two standard algorithms for shortest path problems:

  1. The conventional dynamic programming algorithm for the shortest path between two given nodes of a directed acyclic networks.
  2. As above but for shortest paths between all pairs of nodes.
  3. Dikjstra's algorithm (allows cyclic network, provided the arc lengths are not negative).

Needless to say, it would be nice to be able to use in this context a graphical user interface capable of handling small networks. Hopefully, such a facility will be ready soon (before the end of the year). Our plan is to begin with the DP algotrithm first, using a "matrix" facility rather than a graphical facility. When the graphical user interface will be ready we shall expand the DP model and then begin work on Dijkstr's algorithm.

Conventional DP for a given pair of nodes

This algorithm is straightforward application of the following functional equation: Let Nodes denotes the set of nodes under consideration and let (s,d) denote the (source, destination) pair of interest. Also, let P(n) denote the set of immediate predecessors of node n, and let

f(n) : = length of shortest path from node s to node n, n in Nodes.

Then the following must hold:

f(n) = min { DM[j,n] + f(j): j in P(n) } , n in Nodes

where DM[i;j] denotes the length of arc (i,j). Here we rely on the convention that the min over an empty set is equal to infinity.

We solve the above functional equation by enumerating the nodes so that f(n) is computed after f(j) has computed for all j in P(n). The process starts at n=s with f(s)=0 and terminates when f(d) is computed.

There are two obvious degenerate cases: (1) node s does not have any successor and (2) node d does not have any predesessors. In both cases there is no path connecting node s to node d.