Problem                                             (Carol Zander, CSS 343)
-------

Use Dijkstra's shortest path algorithm to find the shortest path from
the source node 1 in this example, to every other node.


      ____________________         Let source = 1
     /        25          \       
    |                      | 
    |                      |
    |                      v
          10         40     
    2 <------- 1 --------> 6  
               | \            
    |          |   \       | 
    |25        |     \     |
    |          |      \    |50   
    |        30|    100\   |    
    v          |        \  v   
          10   |         >    
    3 ---------|---------> 5 
               |            
    ^          |           ^
    |          v           |   
    |                      |
     \________ 4 _________/   
         20         20       
                            

In case this is hard to read, here is the adjacency cost matrix, C.
A dash is for infinity.

matrix C:    1   2   3   4    5   6   ("--" is for infinity.)

         1  --  10  --  30  100  40
         2  --  --  25  --   --  25
         3  --  --  --  --   10  --
         4  --  --  20  --   20  --
         5  --  --  --  --   --  --
         6  --  --  --  --   50  --

list C:                           (Edges shown as to-node,cost)
         1: 2,10 --> 4,30 --> 5,100 --> 6,40
         2: 3,25 --> 6,25
         3: 5,10 
         4: 3,20 --> 5,20
         5: 
         6: 5,50 

Operation of Dijkstra's algorithm
---------------------------------
// A curvey line, \ with /, means a node is marked as visited below.
// A value is replaced if T[v].dist + (edge cost from v to w) < T[w].dist.
// Comments refer to the computation of the "for each w adjacent to v" loop.
// While the T[k].dist is shown as a table, it is only one row where
//   each successive value shown replaces the previous value above it.

        k: 1   2    3    4    5
T[k].dist: 0  inf  inf  inf  inf  // all are infinity except source to zero
    v = 1  \  50   20   inf  30   // choose v=1: of unmarked, 0 is low
           /                      
    v = 3  \  40    \   60   30   // choose v=3: of unmarked, 20 is low
           /        /
    v = 5  \  40    \   55    \   // choose v=5: of unmarked, 30 is low
           /        /         /     
    v = 2  \   \    \   50    \   // choose v=2: of unmarked, 40 is low
           /   /    /         /
         done done done done done   

Final:     0  40   20   50   30

"for each unvisited w adjacent to v" loop:

        T[w].dist T[v].dist+cost:v->w  Action
        --------- -------------------  ------
v=1                                   mark v=1 visited, never go there again
   w=2     inf        0    +   50     replace inf with 50
   w=3     inf        0    +   20     replace inf with 20
   w=5     inf        0    +   30     replace inf with 30

v=3                                   mark v=3 visited, never go there again
   w=2      50       20    +   20     replace 50 with 40
   w=4     inf       20    +   40     replace inf with 60

v=5                                   mark v=5 visited, never go there again
   w=2      40       30    +   20     leave alone, not shorter through 5
   w=4      60       30    +   25     replace 60 with 55

v=2                                   mark v=2 visited, never go there again
   w=4      55       40    +   10     replace 55 with 50


Here is how the .path changes:
        k: 1   2    3    4    5
T[k].path: 0   0    0    0    0   
    v = 1  \   1    1    0    1   // when v is chosen to be 1
           /                      
    v = 3  \   3    \    3    1   // when v is chosen to be 3
           /        /
    v = 5  \   3    \    5    \   // when v is chosen to be 5
           /        /         /     
    v = 2  \   \    \    2    \   // when v is chosen to be 2
           /   /    /         /
         done done done done done   

Final:     0   3    1    2    1


To extract the path from this information, use a simple recursive function,
printing on the way back. Here's the idea behind it -- suppose you want
the path from the source 1 to 4. Consider 4:

     To get to 4, look at the contents of T[4].path, which is 2.
     This says you get to 4 through 2. So, how do you get to 2?

     To get to 2, look at the contents of T[2].path, which is 3.
     This says you get to 2 through 3. So, how do you get to 3?

     To get to 3, look at the contents of T[3].path, which is 1.
     This says you get to 3 through 1. So, how do you get to 1?

     To get to 1, look at the contents of T[1].path, which is 0.
     Base case. Stop at zero.

All the numbers are  4  2  3  1  which is the path backwards.