1. Shortest Path Algorithm

Given a weighted graph, and node X, find the shortest path from X to each node in the graph.

Our algorithm is a modified version of our traversal algorithm. The algorithm is originally due to Dijkstra, although the presentation below is phrased in a slightly different manner than the textbook's description of Dijkstra's algorithm.

When we add a node to READY, we will store along with the node some extra information: the path (sequence of nodes) that has just led to the node, and the length of this path.

Thus, each entry on READY will be a triple: <Node Name, Path, Path Length>, abbreviated <N,P,L>.

READY will be a priority queue: the ``priority'' of an entry is its Path Length, the entry with the smallest Path Length is the next one removed.

We need to modify our strategy for marking nodes as REACHED. In the traversal algorithms, we could ignore a node the moment it was added to the READY list. But the very first path we find to a node may not be the shortest path, so we will leave the node marked as NOT REACHED until we are sure we have reached it via the shortest path (starting at node X). As it will turn out, we will know the shortest path to node N the moment an entry for node N is removed from the READY list: it is at this point that will mark N as REACHED.

In fact, the term REACHED is not an appropriate word now; we will instead mark nodes as `processed' or `unprocessed'.

Finally, when we go to add a node to READY we look to see if it is already on READY. If it is, we compare the new triple with the one already there, and keep whichever one has the shorter path length.

shortest path algorithm

1. X is your starting point. Place <X, empty path, 0> on READY.

2. pick the triple, <N,P,L> on READY such that L is minimum.
   • Process it. (print ``the shortest path from X to N is P of length L'')

   • Remove it from READY, and mark it as `processed'.

   • Look up N's neighbours {N1, N2...Nk}. These are connected to N by edges that have weights W1,W2,...Wk. Ignore those that are `processed'.

     For each neighbour Ni that is `unprocessed':

     • create the triple <Ni,(P^Ni),L+Wi> (where P^Ni means add node Ni to the end of path P)

     • add this triple to READY - if there is already a triple for Ni on READY, only add the new one (and delete the old one) if its path length is shorter.

3. repeat 2 until READY is empty.

Example: shortest paths from A to all nodes.

• Step 1: READY = [<A,`A',0>].

• Step 2: Process A, mark it `processed'. READY = [<B,`A-B',7>,<C,`A-C',2>]

• Step 2: Process C, mark it `processed'. C's unprocessed neighbours are B and D. Make up a triple for each of them: <B,`A-C-B',6> <D,`A-C-D',7>. Add these to READY if the node name is not already there, or if it is there but the new triple has a shorter path length.

  In this case, we add the new D triple because D is new, and the new B triple because it has shorter path length than the one already on READY.

  READY = [<B,`A-C-B',6>, <D,`A-C-D',7>]

• Step 2: Process B, mark it `processed'. B's sole unprocessed neighbour is D. Create the triple <D,`A-C-B-D',9>. This is not added to READY because there is already a D-triple there that has shorter path length.

  READY = [<D,`A-C-D',7>]

• Step 2: Process D, mark it `processed'. D has no unprocessed neighbours. READY = [] (i.e. empty).

• the shortest path from A to A is `A' of length 0
• the shortest path from A to C is `A-C' of length 2
• the shortest path from A to B is `A-C-B' of length 6
• the shortest path from A to D is `A-C-D' of length 7