Page 313, Exercise 9

The ShortestPath algorithm produced the following distances and paths for Figure 6.36.

 Vertex         Distance     Path 


 
  0              0 
  1              2          0 1 

  2              3          0 2  

  3              6          0 1 3  

  4              7          0 1 3 4  

  5              8          0 1 3 5   

  6              9          0 1 3 4 6 

The only path that is correct is the one between 0 and 2; all of the remaining paths are erroneous.  The problem is the negative path between vertices 1 and 2.  Since vertex 1 has the smallest distance it is initially picked, and all vertices descendant from vertex 1 will use its distance from vertex 0 to determine their own paths.  However, there is a smaller path from vertex 0 to vertex 1, which is obtained by going through vertex 2.  Since the initial selection only examines direct paths, smaller indirect paths are ignored.  The correct paths and distances for
Figure 6.36 should be:

 Vertex         Distance     Path 



  0              0
  1              1            0 2 1 
  2              3            0 2
  3              5            0 2 1 3 
  4              6            0 2 1 3 4 
  5              7            0 2 1 3 5 
  6              8            0 1 2 3 4