DIJKSTRA'S ALGORITHM

void dijkstra(graph g, tree& t, node root) 
   vertex v, w
   edge e 
   heap h
   t.edges := empty
   t.nodes := {root}
   h.makeheap(g.incident(root))    //  can use repeated inserts
   do   (e  :=   h.deletemin())  $\neq$  empty     $\rightarrow$ 
      t.edges  :=  t.edges $\cup$ {e} 
      v  := e.new_node
      t.nodes  :=  t.nodes $\cup$ {v}
      for w  $\in$  g.adj(v)   $\rightarrow$  
         if  w $\mbox {$\space \; \not \in \; $}$  t.nodes and w $\mbox {$\space \; \not \in \; $}$  h   $\rightarrow$  
            e.old_node := v
            e.new_node := w
            e.dist := t.dist(v)+ g.cost(v, w)
            h.insert(e) 
         | w  $\in$  h and g.cost(v,w) + t.dist(v) < h.dist(w)  $\rightarrow$  
            h.changekey(w, (t.dist(v)+g.cost(v,w)), v)
         fi 
      rof  
   od
end dijkstra