Dijkstra Algorithm

Consider each node with a tag associated as (flag, previous, distance); where flag is true if the node is made permanent else false, previous indicates the name of the previous node and distance is the distance of the current node from the start node.

Algorithm 1 (To set the traversal path and find minimum distance)

1. Set  the tags of all the nodes as (F, -, infinity) i.e.
   F -> permanent false
   (dash - ) -> No previous node and
   distance is infinity
2. Accept the start node and set the tag for the start node as (T, -, 0) i.e.
   permanent
   No previous node and
   distance is 0
3. Set the tags of all reachable nodes from start node; previous node is start node and distance from the start node
4. Find  a node with minimum distance and permanent = false; Note: don’t compare with nodes having distance infinity
5. If no such node exists then go to step 9
6. Mark this node permanent i.e. set the permanent flag true
7. Find all reachable nodes from this node
   Dist = this.distance + distance of reachable node from this node
   If distance of the new node is infinity then
   Set the distance = Dist
   Set the previous node = this
   Else
   If (reachable.distance>Dist) then
   Set the distance = Dist
   Set the previous node = this
   End If
   End If
8. Go to Step 4
9. Print traversal path and distance of each node from start node
10. Stop

Algorithm 2 (Print traversal path and distance of each node from start node)

1. Take a node from the tree
2. Print the distance value from tag
3. Print current nod name
4. If distance=0 then go to step 7
5. Current = Current.previous
6. Go to step 3
7. Take next node
8. If node exists then go to step 2
9. Stop