dijkstra

Dijkstra’s Algorithm

• Requires non-negative weights.
• Uses min-priority queue to keep track of next vertices to consider.
• Always chooses the “lights” or “closes” vertex in $Q$ to insert into $S$, hence a greedy algorithm.
• If the min-priority queue is implemented by
  • An array, $O(V^2)$
  • A binary heap, $O((V+E)\lg V)$
  • A Fibonacci heap, $O(V\lg V+E)$

DIJKSTRA(G, w, s)
    INITIALIZE-SINGLE-SOURCE(G, s)
    S = {}
    Q = {}
    for each vertex u in G.V
        INSERT(Q, u)
    while Q != {}
        u = EXTRACT-MIN(Q)
        S = S + {u}
        for each vertex v in G.Adj[u]
            RELAX(u, v, w)
            if the call of RELAX decreased v.d
                DECREASE-KEY(Q, v, v.d)