Shortest path in undirected graph
- Files in the project
- project.c
c source code - data.txt
Please referring general help for details. - run.bat
Please referring general help for details.
- project.c
- Compile and execute
- Compile
You only need to compile project.c - Execute
If executable (compiled) file is project.exe executing command is*project.exe data.txt A M*
Please referring general help for more.
- Compile
- Understand source code
- Read data file
Please referring general help for details.
- 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 - Field
*chNodePrevious*and*iWeightToStart* They are very important, please see bellow.
- Field
- Key process:
**fixed set**and**tentative set**(see example)- 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). - put start node in fixed set:
start.chNodePrevious=start; start.iWeightToStart=0; - 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.
- "total weight" between 2 nodes which are in 2 sets
- initialize all nodes in tentative set and their weight
as infinite.
- 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.
- Thinking about
Can you find advantage and disadvantage if we delete field iWeightToStart in struct Path?
- Read data file
Example:Lets use graph above as example to explain: Assume we want to to find shortest path from A to M -
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
- 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,*) - 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,*)
- 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 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||