// Input: a undirected graph G s.t.
// for all edge e, e.cost is a non negative real number
// and a starting node n
//
// Output: a modified graph G s.t. for all nodes m reachable
// from n in G, n.backpointer points to the previous node
// in a path of minimal cost from n to m
//
// Dijkstra(G,n) \in O(|V| + |E|*log|V|)
Dijkstra(G,n) {
   Q = EmptyPriorityQueue(|V|) // or Heap; |V| is the size of the array to avoid running out of space
   n.backpointer := NIL
   n.cost := 0
   Add(Q,n,0)
   while not Empty(Q) do
     m:= Min(Q)                                         // executed once per node
     for each u in AdjSet(G,m) with cost k do
        if m.cost + k > u.cost then                     //
          u.cost := m_cost + k                          // executed twice per edge
          AddOrUpdateCost(Q,u,u.cost)                   //
}

// When n is put in the heap in position i in the array,
// n.position is put to i. Assuming that when it is removed
// or at the beginning of the algorithm n.position = -1 then
// the check BelongsToPriorityQueue(Q,n) can be done in O(1)
// by checking if n.position <> -1
//
// AddOrUpdateCost \in O(log |V|)
AddOrUpdateCost(Q,n,k) {
   if BelongsToPriorityQueue(Q,n) then
      Remove(Q,n)
      Add(Q,n,k)
   else
      Add(Q,n,k)
}