Give the start vertex the permanent label ‘0’.
Find all vertices directly connected to the vertex you have just given a permanent label to.
Give each of these the temporary label.
Temporary label = Permanent label of previous vertex + Weight of arc joining them
If temporary label is already occupied, replace it only if the new value is lower.
The temporary label without a permanent label which has the lowest value is the next permanent label.
Repeat until end vertex has a permanent label.
Find route from start vertex to end vertex.
Order of becoming permanent | Permanent label |
Temporary Labels |
ABCG is the shortest path.
©2011 Grant Dwyer
No comments:
Post a Comment