Dijkstra's algorithm

Procedure

DIJKSTRA(G, w, s):
    INITIALIZE-SINGLE-SOURCE(G, s)
    S = ∅
    Q = G.V
    while Q != ∅:
        u = EXTRACT-MIN(Q) // greedy here
        S = S ∪ {u}
        for each vertex v ∈ G.Adj[u]:
            RELAX(u, v, w)

INITIALIZE-SINGLE-SOURCE(G, s):
    for each vertex v ∈ G.V:
        v.d = ∞
        v.π = NIL
    s.d = 0

RELAX(u, v, w):
    if v.d > u.d + w(u, v):
        v.d = u.d + w(u, v)
        v.π = u

The operation EXTRACT-MIN can be implmented by HEAP-EXTRACT-MIN in setting of priority queue.

Reference(s)

• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: The MIT Press, 2009.