Dijkstra's Algorithm: Shortest Path

Dijkstra's Algorithm

• Designed to find the shortest paths in a graph.
• Applicable to both directed and undirected graphs.
• Requires all edges to have non-negative weights.
• Classified as a greedy algorithm.
  • Maintains a set S of vertices with determined shortest path weights from source s.
  • Selects vertex u from V - S with the minimum shortest path estimate iteratively.
  • Adds u to S.
  • Relaxes all edges leaving u.

Relaxation Process

• Each vertex v has a shortest path estimate d[v] from source s.

• Initially, d[v] is set to infinity for all vertices.

• Relaxing edge (u,v) optimizes the shortest path to v by checking the path through u.

  Relax (u,v,w)
      if d[v] > d[u] + w(u,v)
         then d[v] := d[u] + w(u,v)
  

Algorithm Steps

DIJKSTRA(G,w,s)
    INITIALIZE-SINGLE-SOURCE(G,s)
    S := 0
    Q := V[G]
    while Q != 0
        do u := EXTRACT-MIN(Q)
           S := S U {u}
           for each vertex v ∈ Adj[u]
               do RELAX(u,v,w)

Complexity Analysis

• Min-priority queue Q implementation influences the algorithm's complexity significantly.
• When using an array, complexity is O(V^2 + E) = O(V^2) because EXTRACT-MIN takes O(V) time.
• With a binary heap, the complexity becomes O((V+E)lgV) = O(ElgV) since EXTRACT-MIN takes O(lgV) time.
• Implementing with a Fibonacci heap yields a complexity of O(VlgV + E) because EXTRACT-MIN has O(lgV) amortized time.

Example Walkthrough

Correctness Theorem

• Dijkstra's algorithm leads to an optimal solution, despite its greedy approach.
• Theorem: The algorithm concludes with d[v] = σ(s,v) for all vertices v in V, where σ(s,v) represents the shortest path weight from s to v.

Comprehensive Proof

• Initialization: At the start, d[s] = 0 and d[v] = ∞ for all v in V - {s}, satisfying all vertices trivially.
• Maintenance:
  • Let u be the first vertex where d[u] ≠ σ(s,u), and u ≠ s because d[s] = 0 = σ(s,s).
  • There is a path from s to u; otherwise, d[u] = ∞ = σ(s,u).
  • A vertex x precedes u on the shortest path from s to u, with x in S and y in V - S.
  • Thus, σ(s,u) = σ(s,y) + σ(y,u).
  • Because u is the first vertex with d[u] ≠ σ(s,u), then d[y] = σ(s,y).
  • Since all edge weights are non-negative, σ(s,y) ≤ σ(s,u), hence d[y] ≤ σ(s,u).
  • Since u was selected before y, d[u] ≤ d[y], implying d[u] ≤ σ(s,u).
  • Because d[u] can never be less than σ(s,u), d[u] = σ(s,u), proving the algorithm's correctness.

Final Thoughts

• Dijkstra's algorithm effectively finds shortest paths in graphs with non-negative edge weights.
• Its complexity is heavily determined by the min-priority queue implementation:
  • O(V^2) with an array.
  • O(ElgV) with a binary heap.
  • O(VlgV + E) with a Fibonacci heap.