Stepwise procedure of Dijkstra’s algorithm
Step 1 : Source node is initialized and can be indicated as filled circle.
Step 2 : Initial path cost to neighboring nodes (adjacent nodes) or link cost is computed and these nodes are relabeled considering source node.
Step 3 : Examine all adjacent nodes and find smallest label, make it permanent.
Step 4 : The smallest label is now working node, then Step 2 and Step 3 are repeated till the destination node is reached.
Following Example illustrated Dijkstra’s algorithm:
An undirected graph is shown in figure.
figure. a
To find shortest path from A to D, we start by making node A as permanent. Then find each node adjacent to A, re-labeling each one with the distance to A. Whenever a node is rebelled, we label it with node so that it reconstructs the final path later. After examining each of nodes adjacent to A, we examine all the tentatively labeled nodes in the whole graph and make the one with the smallest label permanent as shown in fig. (b) This one becomes the new working node.
figure. b
Now at B, examine all the nodes adjacent to it. If the sum of the label on B and distance from B to the node being considered is less than label at that node, we have shortest path so that node is labeled.
After all nodes adjacent to the working node have been impacted and tentative tables changed, the entire graph is searched for the tentatively labeled node with the smallest value. This node is made permanent and becomes the working node for the next round.
If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.