Dijkstra's Algorithm

  1. Label node 1 (start node) with a permanent 0.
  2. Temporarily label each node i that is connected to 1 with the length of the arc joining 1 and i.
  3. Choose the node with the smallest label and make it permanent.*
  4. If node i has just become the (k+1)th node to be given a permanent label, this is the kth closest node to 1.
  5. For each temporary node j that can be reached via i, replace its temporary label by min {j's current temporary label, node i's perm label + distance (i,j)
  6. Make the smallest temporary label permanent.
  7. Repeat until you reach the goal node.
*You also need to note the preceding node when you make a label permanent.