Dijkstra’s Algorithm: A Comprehensive Guide

Before directly jumping to Dijkstra’s Algorithm, let’s first understand some basic concepts related to it.

Weighted Graph

A weighted graph is a network of vertices (nodes) connected by edges, where each edge has a weight. The weight is a numerical value representing cost, distance, time, capacity, or any other metric associated with traversing that edge. The weights tell you the cost of using that edge.

Real-world Examples:

• Social Networks: People are nodes, friendship connections are edges, and relationship strength is the weight.
• Flight Routes: Airports are nodes, flights are edges, and ticket price or flight duration is the weight.
• Road Networks: Cities are nodes, roads are edges, and distance or travel time is the weight.

Key Graph Terms:

Term	Definition
Path	A sequence of edges connecting two vertices.
Shortest Path	The path between two vertices that has the minimum sum of edge weights.

---

What is Dijkstra’s Algorithm?

Dijkstra’s Algorithm is the classic greedy algorithm designed to solve the single-source shortest path problem on a weighted graph.

Problem Statement:

• Given: A weighted graph with non-negative edge weights and a starting source vertex (s).
• Find: The shortest path from (s) to every other reachable vertex in the graph.
• Output:
• dist[]: An array where dist[v] is the shortest distance from source (s) to vertex (v).
• parent[]: An array where parent[v] holds the predecessor of (v) on the shortest path (used for path reconstruction).

Real-world Analogy (GPS Navigation):

Imagine you are at home, and Google Maps needs to find the fastest route to a restaurant. Google’s servers run Dijkstra’s algorithm on a road network graph where each road’s weight is the travel time. In a single run, Dijkstra computes the fastest path not just to your chosen restaurant, but to every reachable location from your house. This is why Google Maps can instantly show you alternative routes and arrival times to nearby places‚Äîthey are all computed at once!

Intuition (The Water Flood Analogy):

Imagine water flooding a network of pipes from your starting location. The water spreads in all directions simultaneously but travels faster through shorter, lower-resistance paths. The first moment water reaches a city is guaranteed to be the fastest path. Dijkstra’s algorithm simulates this process step-by-step.

---

Step-by-Step Algorithm

1. Initialization:

1. Set dist[source] = 0 and dist[v] = ∞; for all other vertices (v).
2. Set parent[v] = null for all vertices.
3. Create an empty priority queue (min-heap) pq and push (0, source) into it.
4. Keep track of visited nodes using an empty set or array.

2. Main Loop:

While the priority queue pq is not empty:

1. Extract the pair (distance, u) with the minimum distance.
2. If u is already visited, skip it.
3. Mark u as visited.
4. For each neighbor v of u:

• Calculate new_distance = dist[u] + weight(u, v).
• Relaxation Step: If new_distance < dist[v]:
  • Update dist[v] = new_distance.
  • Update parent[v] = u.
  • Push (new_distance, v) into the priority queue.

---

Pseudocode

Algorithm: Dijkstra(graph, source)
Input: A graph with vertices and weighted edges, and a starting vertex source
Output: dist[] (shortest distances) and parent[] (predecessor path trackers)

for each vertex v in graph:
    dist[v] = INFINITY
    parent[v] = NULL

dist[source] = 0
priority_queue pq = empty min-heap
pq.push((0, source))
visited = empty set

while pq is not empty:
    current_dist, u = pq.pop()  # Extract the vertex with the minimum distance

    if u in visited:
        continue  # Skip already processed vertices

    visited.add(u)

    for each vertex v adjacent to u:
        weight = edge_weight(u, v)

        # Relaxation Step
        if dist[u] + weight < dist[v]:
            dist[v] = dist[u] + weight
            parent[v] = u
            pq.push((dist[v], v))

return dist, parent

---

Walkthrough Example

Graph Definition:

• Vertices: A, B, C, D, E
• Edges: A-B (4), A-C (2), B-C (1), B-D (5), B-E (6), C-D (8), C-E (10), D-E (2)

Step 1: Initialization

dist:    [A:0, B:∞, C:∞, D:∞, E:∞]
parent:  [A:null, B:null, C:null, D:null, E:null]
visited: []
pq:      [(0, A)]

Step 2: Process A

• Extract (0, A) from pq and mark A as visited.
• Explore A‘s neighbors:
• B: 0 + 4 = 4 < ∞. Update dist[B] = 4, parent[B] = A.
• C: 0 + 2 = 2 < ∞. Update dist[C] = 2, parent[C] = A.

dist:    [A:0, B:4, C:2, D:∞, E:∞]
visited: [A]
pq:      [(2, C), (4, B)]

Step 3: Process C

• Extract (2, C) from pq and mark C as visited.
• Explore C‘s neighbors:
• A: Already visited, skip.
• B: 2 + 1 = 3 < 4. Update dist[B] = 3, parent[B] = C.
• D: 2 + 8 = 10 < ∞. Update dist[D] = 10, parent[D] = C.
• E: 2 + 10 = 12 < ∞. Update dist[E] = 12, parent[E] = C.

dist:    [A:0, B:3, C:2, D:10, E:12]
visited: [A, C]
pq:      [(3, B), (4, B), (10, D), (12, E)]

Step 4: Process B

• Extract (3, B) from pq and mark B as visited.
• Explore B‘s neighbors:
• A, C: Already visited, skip.
• D: 3 + 5 = 8 < 10. Update dist[D] = 8, parent[D] = B.
• E: 3 + 6 = 9 < 12. Update dist[E] = 9, parent[E] = B.

dist:    [A:0, B:3, C:2, D:8, E:9]
visited: [A, C, B]
pq:      [(4, B), (8, D), (9, E), (10, D), (12, E)]

Step 5: Process D

• Extract (4, B) from pq. Since B is already visited, skip.
• Extract (8, D) from pq and mark D as visited.
• Explore D‘s neighbors:
• B, C: Already visited, skip.
• E: 8 + 2 = 10 > 9. No update needed (9 is already shorter).

dist:    [A:0, B:3, C:2, D:8, E:9]
visited: [A, C, B, D]
pq:      [(9, E), (10, D), (12, E)]

Step 6: Process E

• Extract (9, E) from pq and mark E as visited.
• E has no unvisited neighbors.

dist:    [A:0, B:3, C:2, D:8, E:9]
visited: [A, C, B, D, E]
pq:      empty

Final Results (Shortest Path from A):

• A → A: Cost: 0
• A → B: Cost: 3 (Path: A → C → B)
• A → C: Cost: 2 (Path: A → C)
• A → D: Cost: 8 (Path: A → C → B → D)
• A → E: Cost: 9 (Path: A → C → B → E)
• Path Reconstruction to E: E ← B ← C ← A (Reverse order of parents).

---

Complexity Analysis

Time Complexity:

• With Binary Min-Heap: (O((V + E) log V))
• (V) insertions/extractions from the heap: (O(V log V))
• (E) relaxation operations (decrease-key): (O(E log V))
• With Array (Linear Search): (O(V^2))
• Preferred for extremely dense graphs where (E \approx V^2).
• With Fibonacci Heap: (O(E + V log V))
• High constant factor; primarily of theoretical interest and rarely used in production.

Space Complexity:

• (O(V + E)) to store the graph adjacency list representation.
• (O(V)) helper storage for dist[], parent[] tracking, and the priority queue states.

---