Monday 5 September 2011

Dijkstra's Algorithm


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