STATEMENT OF DYKSTRAS ALGORITHM


   ASSUME:  n nodes labeled 1, 2, ..., n, and edges between the nodes, each with 
   a positive cost.  One of the nodes is labeled as StartNode.  

   INF is a constant denoting infinity.  In an actual program, it has some very 
   large value like 999999.

   Let T(N) denote the total cost (tentative or permanent) of all the edges from
   StartNode to N.

   VALUES STORED AT EACH NODE:

   The bool value named IsPermanent.
   An int value named TotalCost.  

   IsPermanent is set to true when the total cost from StartNode to the node is known.
   Before a node is made permanent, the total cost is only tentative.

   
   Last is the node that was made permanent in the last iteration.


   GOAL:   Find the total cost of the path from the start node to each of
   the nodes in the graph.

   ALGORITHM:

   Initialize TotalCost for each node to INF.
   Initialize IsPermanent for each node to false.
   Set TotalCost for the StartNode to 0.
   Set IsPermanent for StartNode to true.
   Set Last to StartNode.
   While some nodes not permanent:
      Find the node N connected to Last that gives the minimum value of
          c = min(T(Last) + Cost of edge from Last to N, T(N))
      Change TotalCost for N to c.
      Change IsPermanent for N to true.
      Set Last to N.
   End While.

   
 
   PROOF THAT DYKSTRA WORKS

        The proof is by induction of the number of permanent nodes used
   to find the minimum cost path.  Assume that all the edge weights are
   nonnegative.

        BASIS CASE.  One permanent node used.  This means that the 
   start node equals the destination node so the minimum cost path has
   cost 0.  (No edge is needed so no cost is involved.)

        INDUCTION CASE.  Assume Dykstra finds the minimum cost path when
   n-1 permanent nodes are used.  Prove that it also finds the minimum cost 
   path for n permanent nodes.

        Let S be the start node and let L be the node made permanent at
   iteration n. (There are now n permanent nodes.)  Suppose that the 
   path D that Dykstra finds is not minimum cost.  Then there is another
   path E = S, ..., Z, L that is of lower cost.  Let T(N) represent the total
   cost of node N found by Dykstra and let c be the cost of the edge joining 
   Z and L.

        CASE 1. Z is a permanent node.  Then the path E has already been
   checked by Dykstra.  If E were really the minimum cost path, Dykstra
   would have chosen it instead of D.  This is a contradiction.

        CASE 2. Z is not permanent and T(Z) >= T(L).  Then the total 
   cost of path E is T(Z) + c > T(L).  (Here is where we use the fact that
   c > 0.  Therefore D is lower cost than path E, a contradiction.

        CASE 3. Z is not permanent and T(Z) < T(L).  In this case Z
   would have been made permanent before L which is a contradiction.

        Since all three cases lead to contradictions, the assumption
   that E is lower cost than D must be incorrect, so D is the minimum
   cost path from S to L.