Skip to content

Dijkstra's Algorithm

Summarized notes on Introduction to Algorithms, Chapter 24

  • input is weighted, directed graph where edge weights are nonnegative
  • depending on implementation, can be faster than Bellman-Ford
  • idea: maintain set \(S\) of vertices whose shortest path weights from \(s\) are already determined
    • maintains loop invariant \(Q = V - S\)
    • initially \(S\) is empty set
    • \(u\) has the smallest shortest-path estimate of any vertex in \(V-S\)
    • on each iteration add \(u\) to \(S\)
  • Running time depends on implementation of priority queue

Pseudo code implementation

1
2
3
4
5
6
7
8
9
Dijkstra(G, w, s)
    Initialize-single-source(G, s)
    S = emptyset
    Q = G.V
    while Q != emptyset
        u = Extract-min(Q)
        S = S union {u}
        for each vertex in G.adj[u]
            Relax(u, v, w)

Complexity

Running Time
\(O(V^2)\) array as queue
\(O(E \lg V)\) binary min-heap
\(O(V \lg V + E)\) Fibonacci heap