|
Shortest path in undirected graph
Download source code and project.
- 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.
- 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
A and M are start and destination nodes, you can change to other nodes.
Please referring general help
for more.
- 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 stores name of a node. i.e. for node W, W.chNode=W;
- Field chNodePrevious and iWeightToStart
They are very important, please see bellow.
- 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.
This is a loop process until destination node is moved to fixed set.
- 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?
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,*) |
|
Congratulations! we can stop now because destination node M has been flaged
to
fixed set.
- 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
|