Type the DIJKSTRA pseudocode

Answer

DIJKSTRA(G, w, s): INITIALIZE-SINGLE-SOURCE(G, s) S = {} Q = G.V # min-priority queue on d while Q is not empty: u = EXTRACT-MIN(Q) S = S union {u} for each v in G.Adj[u]: RELAX(u, v, w) # DECREASE-KEY if v.d dropped

Each EXTRACT-MIN commits one vertex with its final distance (the squeeze proof, valid only for nonnegative weights). Relaxing its out-edges may improve neighbors still in Q.