Lecture 12 - Shortest Path Algorithm

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.

  3. repeat 2 until READY is empty.

Example: shortest paths from A to all nodes.

        
The result of all this is the output: