Shortest Path Algorithm: Dijkstra's Algorithm

Shortest Path Algorithm: Dijkstra's Algorithm

Description
Dijkstra's algorithm is used to solve the single-source shortest path problem in a weighted directed graph, i.e., finding the shortest paths from a given source vertex to all other vertices in the graph. The algorithm requires that edge weights be non-negative. Its core idea employs a greedy strategy, iteratively determining the vertex closest to the source and using these vertices to update the shortest distances to their neighbors.

Solution Process

Step 1: Initialize Distance Array

  • Create an array dist[] to record the current shortest distance from the source to each vertex. Initially, set the source distance to 0 (i.e., dist[source] = 0) and the distances of all other vertices to infinity (indicating unreachable).
  • Create a priority queue (min-heap) or set to dynamically select the vertex with the current minimum distance. Initially, add the source vertex to the queue.

Step 2: Select Vertex with Current Minimum Distance

  • Remove the vertex u with the smallest dist value from the queue (the first removal will inevitably be the source). At this point, the shortest distance to u is confirmed (greedy choice: since all edge weights are non-negative, a shorter path via another route is impossible).
  • If the queue is empty, the algorithm terminates.

Step 3: Relaxation Operation (Update Neighboring Vertex Distances)

  • Traverse all adjacent vertices v of vertex u and check if a shorter path exists:
    If dist[u] + weight(u, v) < dist[v], then update dist[v] = dist[u] + weight(u, v) and add v to the queue (if using a heap, the heap structure needs adjustment).
  • This step ensures that transiting through u may shorten the distance to v.

Step 4: Repeat Steps 2-3

  • Repeat the above process until all vertices have been processed (i.e., the queue is empty). The final dist[] array stores the shortest distances from the source to each vertex.

Key Details

  1. Non-negative Weight Requirement: If negative-weight edges exist, the greedy choice may fail because a negative-weight edge could provide a shorter path to a vertex whose shortest distance was already considered final.
  2. Time Complexity:
    • Using array traversal to select the minimum vertex: O(V²) (suitable for dense graphs).
    • Using a min-heap: O((V+E)logV) (suitable for sparse graphs).
  3. Path Recording: A prev[] array can be used to record predecessor nodes on the path, allowing reconstruction of the full path by backtracking.

Illustrative Example
Consider the graph: vertex set {A, B, C, D}, edge weights A→B(4), A→C(2), B→C(1), B→D(5), C→D(8). Source vertex is A:

  1. Initial dist[A]=0, others ∞.
  2. Take A, update B=4, C=2.
  3. Take C (current minimum), via C update D=2+8=10.
  4. Take B, via B update C=min(2, 4+1)=2 (unchanged), update D=min(10,4+5)=9.
  5. Final dist[D]=9, path A→B→D.

Through iterative greedy selection, the algorithm ensures that each expanded vertex has the shortest possible distance, ultimately yielding the global optimal solution.