Shortest path in undirected graph

Download source code and project.


  • Files in the project
    1. project.c
      c source code
    2. data.txt
      Please referring general help for details.
    3. run.bat
      Please referring general help for details.
            
  • Compile and execute
    1. Compile
      You only need to compile project.c
    2. Execute
      If executable (compiled) file is project.exe
      executing command is project.exe data.txt A M
      A and M are start and destination nodes, you can change to other nodes.
      Please referring general help for more.
         
  • Understand source code
    1. Read data file
      Please referring general help for details.
          
    2. struct Path
      The program uses an array of the struct in size of 26 - Path path[26] - to store all nodes from A to Z.
      • Field iExist 
        which indicates if the node exists, i.e. if node U is not in graph, U.iExist=0. otherwise U.iExist=1;
      • Field chNode  
        which
        stores name of a node. i.e. for node W, W.chNode=W;
      • Field chNodePrevious and iWeightToStart 
        They are very important, please see bellow.
         
    3. Key process: fixed set and tentative set (see example)
      1. initialize all nodes in tentative set and their weight as infinite.
        node.chNodePrevious=0;
        node.iWeightToStart=INFINITE;
        you can use any of these two fields as flag to identify if a node is in fixed set.
        this program uses  field chNodePrevious (0 means in tentative set, otherwise in fixed set).
      2. put start node in fixed set:
        start.chNodePrevious=start;
        start.iWeightToStart=0;
      3. find minimum "total weight" from tentative set to fixed set and 2 nodes involved,
        one of the 2 nodes is in tentative set and another is in fixed set.
        then move the tentative node to fixed set by:
        nodeInTentativeSet.chNodePrevious=nodeInFixedSet;
        nodeInTentativeSet.iWeightToStart=minimum "total weight";

        what does "total weight" between the 2 sets mean?
        lets explain step by step:
        • "total weight" between 2 nodes which are in 2 sets
          it is weight between the 2 nodes plus iWeightToStart of fixed node.  
          actually it is total weight from the tentative node to start node.
        • minimum "total weight" from a tentative node to fixed set.
          it is minimum "total weight" from the node to all fixed nodes.
        • minimum "total weight" between 2 sets
          it is minimum one among minimum "total weight" of all tentative nodes to fixed set.
        This is a loop process until destination node is moved to fixed set.
         
    4. Conclusion
      Key for obtaining shortest path is that all nodes are divided in to two sets, fixed and  tentative sets.
      All nodes are initialized in tentative set except start node, then to find shortest edge from tentative set to fixed set and move related node to fixed set until destination node is moved
      .
       
    5. Thinking about
      Can you find advantage and disadvantage if we delete field iWeightToStart in struct Path?


Example:
Lets use graph above as example to explain:
Assume we want to to find shortest path from A to M
       
  1. Initialize all nodes (in function StartSearch(...))
    chNodePrevious=0; (no previous node connected to the node)
    the field works as flag also to indicate if the node is in tentative set (if 0) or in fixed set
    iWeightToStart=infinite; (a very large number) 
    So nodes in fixed set and tentative set as:
    Fixed                
    Tentative A(0,*) B(0,*) E(0,*) F(0,*) H(0,*) G(0,*) K(0,*) M(0,*)
    note: X(0,*) means chNodePrevious=0 and iWeightToStart=infinite for node X
    At this step, all nodes are in tentative set and fixed set is empty 
     
  2. Initialize chNodePrevious=A and iWeightToStart=0  for node A (start node)
    so node A is flagged to fixed set
    Fixed A(A,0)              
    Tentative   B(0,*) E(0,*) F(0,*) H(0,*) G(0,*) K(0,*) M(0,*)
  3.  
  4. We can start loop process now:
     
  • find minimum "total weight" between 2 sets and related nodes.
    because there is just one node A in fixed set, we compare "total weight" of all nodes in tentative set to node A.
    the node which has minimum "total weight" is F  and minimum "total weight" is 5+0, its previous node is A.
    So move it to fixed set
    Fixed A(A,0)     F(A,5)        
    Tentative   B(0,*) E(0,*)   H(0,*) G(0,*) K(0,*) M(0,*)
      
  • find minimum "total weight" between 2 sets and related nodes again.
    because there are 2 nodes (A and F) in fixed set, we compare "total weight" of all nodes in tentative set to A and F.
    the node found is H, and "total weight" is 8+0, its previous node is A, so move it to fixed set.
    Fixed A(A,0)     F(A,5) H(A,8)      
    Tentative   B(0,*) E(0,*)     G(0,*) K(0,*) M(0,*)
     
  • again.
    we find 2 nodes which have same minimum value:
    B: "total weight" is 12+0=12, previous node is A
    G: "total weight" is 4+8=12. previous node is H.
    "total weight" is edge's weight between 2 nodes plus iWeightToStart of fixed node.
    in other words, "total weight" is total weight of a node to start node.
    we can move B and G to fixed set at same time, but for simple reason, we only move one at one step.
    Lets move G now.
    Fixed A(A,0)     F(A,5) H(A,8) G(H,12)    
    Tentative   B(0,*) E(0,*)       K(0,*) M(0,*)
     
  • once again
    the node is B
    Fixed A(A,0) B(A,12)   F(A,5) H(A,8) G(H,12)    
    Tentative     E(0,*)       K(0,*) M(0,*)
  •  
  • once again
    the node is E, "total weight" is 18+5=23, previous node is F 
    Fixed A(A,0) B(A,12) E(E,23) F(A,5) H(A,8) G(H,12)    
    Tentative             K(0,*) M(0,*)
  •  
  • once again
    the node is M, "total weight" is 13+12=25, previous node is G
    Fixed A(A,0) B(A,12) E(E,23) F(A,5) H(A,8) G(H,12) M(G,25)
    Tentative             K(0,*)   
    Congratulations! we can stop now because destination node M has been flaged to fixed set.
 
  1. Now we have shortest path by "previous" node in fixed set and total weight 25.
    M - G - H - A
    In fact, you should find the path backward so the path by previous node is A - H - G - M
    Also, you should realize that shortest path may be not unique.        

Key words
Dijkstra algorithm
Floyd algorithm