Dijkstra’s Algorithm

# CHAPTER 24

Dijkstra’s Algorithm #

1. Introduction #

2. Learning Objectives #

• Define the "Greedy" logic driving Dijkstra's Algorithm.

• Understand the integration of the Min-Heap (Priority Queue) to extract the cheapest node.

• Execute Edge Relaxation sequentially across a weighted matrix.

• Code a production-ready Dijkstra implementation in Python.

3. The Core Concept (Greedy Min-Heap) #

The Golden Rule: Once Dijkstra pops a Node from the Priority Queue and formally processes it, it permanently locks that node. It assumes it has found the absolute mathematical Shortest Path to that node and will *never* evaluate it again. (This is why it fails on Negative Weights!).

4. Step-by-Step Execution #

The Graph:

• A -> B (Weight 5)

• A -> C (Weight 10)

• B -> C (Weight 2)

The Goal: Shortest path from A to C.

1. 1. Initialize: Distance[A] = 0. All others Infinity. Push (0, A) to Min-Heap.

1. 2. Pop Min-Heap: We get A. Cost is 0.

1. 3. Evaluate Neighbors of A:

• Neighbor B: Path cost is $0 + 5 = 5$. Is $5 < \text{Infinity}$? Yes! Relax Edge. Distance[B] = 5. Push (5, B) to Heap.

• Neighbor C: Path cost is $0 + 10 = 10$. Is $10 < \text{Infinity}$? Yes! Relax Edge. Distance[C] = 10. Push (10, C) to Heap.

1. 4. Pop Min-Heap: The Heap contains (5, B) and (10, C). The absolute cheapest is (5, B). Pop B!

1. 5. Evaluate Neighbors of B:

• Neighbor C: Path cost to B is $5$. Edge from B to C is $2$. Total cost = $5 + 2 = 7$.

• Relaxation Check: Is $7 < \text{Distance}[C]$ (which is currently 10)? YES! We found a shortcut! Overwrite Distance[C] = 7. Push (7, C) to Heap.

1. 6. Pop Min-Heap: We pop (7, C). Target reached. Minimum path is exactly 7!

5. Code Implementation (Python) #

import heapq

def dijkstra(graph, start_node):
    # Initialize distances to Infinity
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0
    
    # Priority Queue: stores tuples of (Cumulative_Cost, Node)
    pq = [(0, start_node)]
    
    while len(pq) > 0:
        # Pop the absolute cheapest node!
        current_distance, current_node = heapq.heappop(pq)
        
        # Optimization: If we found a cheaper path earlier, ignore this bloated frame
        if current_distance > distances[current_node]:
            continue
            
        # Explore neighbors
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            
            # Edge Relaxation!
            if distance < distances[neighbor]:
                distances[neighbor] = distance # Overwrite with cheaper cost
                heapq.heappush(pq, (distance, neighbor)) # Push to Min-Heap
                
    return distances

# Adjacency List: {Node: [(Neighbor, Weight)]}
graph = {
    &#039;A': [('B', 5), ('C', 10)],
    &#039;B': [('C', 2), ('D', 8)],
    &#039;C': [('D', 1)],
    &#039;D': []
}

print(dijkstra(graph, &#039;A'))
# Output: {'A': 0, 'B': 5, 'C': 7, 'D': 8}

6. Complexity Analysis #

• Time Complexity: $O((V + E) \log V)$. Evaluating every edge takes $E$. Extracting and pushing to the Min-Heap takes $\log V$. The combination ensures lightning-fast execution even on dense networks.

• Space Complexity: $O(V + E)$ to store the Graph, plus $O(V)$ for the Distance Array and the Priority Queue.

7. The Negative Weight Fatal Flaw #

8. Common Mistakes #

• Using a standard Queue: If you use a standard FIFO collections.deque instead of a heapq, you have destroyed the entire algorithm. It degrades into a horrific, brute-force BFS that wastes massive CPU cycles evaluating expensive paths blindly.

9. Exercises #

1. 1. Trace Dijkstra's algorithm on the Python graph provided above to find the path to Node D. Why does the algorithm choose the path through C instead of directly from B?

1. 2. Theoretically explain why Dijkstra's algorithm processes unweighted graphs perfectly, but is considered overkill and inefficient compared to standard BFS.

10. MCQs with Answers #

11. Interview Preparation #

• *Algorithmic Debugging:* "In the Python code, there is a line: if current_distance > distances[current_node]: continue. Why is this optimization absolutely critical?" *(Answer: Because Python's heapq does not support $O(\log N)$ dynamic internal value updating! When an Edge Relaxation occurs, we just push a duplicate tuple with the newer, cheaper price into the heap. When the old, expensive, obsolete tuple eventually pops, that if statement catches it and instantly discards it, preventing catastrophic duplicate processing!)*

12. Summary #

13. Next Chapter Recommendation #