Lesson 3 � Intermediate

Dijkstra's Shortest Path

Dijkstra's algorithm ek greedy algorithm hai jo weighted graph mein single source se sab shortest paths nikalta hai. Google Maps se lekar network routing tak yeh use hota hai.

Dijkstra kyun kaam karta hai?

Idea simple hai: har step par sabse kam distance wale node ko pick karo aur uske neighbors ko relax karo (update karo agar shorter path mile). Yeh greedy approach hai � hamesha current best option choose karte hain.

Jaise Google Maps: har junction par sabse kam time lage wala rasta choose karte ho.

Graph with weights:
 A --4--> B --2--> C
 | |
 1 5
 v v
 D ------3-------> E

Shortest paths from A:
A?B: 4, A?C: 6, A?D: 1, A?E: 4

Algorithm Step by Step

1. Source node ka distance 0 rakho, baaki sab ka infinity.
2. Min-heap mein (0, source) push karo.
3. Heap se sabse kam distance wala node nikalo.
4. Agar nikla hua distance stored distance se bada hai toh skip karo (already better path mil chuki hai).
5. Uske sab neighbors ke liye: agar current node se neighbor ka distance kam ho sakta hai toh update karo aur heap mein push karo.
6. Steps 3-5 jab tak heap khali na ho jaye repeat karo.

Python Implementation (Min-Heap)

import heapq

def dijkstra(graph, start):
 dist = {node: float('inf') for node in graph}
 dist[start] = 0
 pq = [(0, start)] # (distance, node)
 
 while pq:
 d, node = heapq.heappop(pq)
 
 # Agar pehle se better path mil chuki hai toh skip
 if d > dist[node]:
 continue
 
 for neighbor, weight in graph[node]:
 if dist[node] + weight < dist[neighbor]:
 dist[neighbor] = dist[node] + weight
 heapq.heappush(pq, (dist[neighbor], neighbor))
 
 return dist

Dry Run

Graph:
A: [(B,4), (D,1)]
B: [(C,2)]
C: [(E,5)]
D: [(E,3)]

Step 1: dist = {A:0, B:8, C:8, D:8, E:8}
 pq = [(0, A)]

Step 2: Pop A (d=0)
 Update B: 0+4=4 < 8 ✓ dist[B]=4
 Update D: 0+1=1 < 8 ✓ dist[D]=1
 pq = [(1,D), (4,B)]

Step 3: Pop D (d=1)
 Update E: 1+3=4 < 8 ✓ dist[E]=4
 pq = [(4,B), (4,E)]

Step 4: Pop B (d=4)
 Update C: 4+2=6 < 8 ✓ dist[C]=6
 pq = [(4,E), (6,C)]

Step 5: Pop E (d=4) � E ke koi unvisited neighbors nahi
Step 6: Pop C (d=6) � C ke koi unvisited neighbors nahi

Final: A:0, B:4, C:6, D:1, E:4

Limitations

• Negative weights nahi chalte: Agar negative weight edge hai toh Dijkstra galat answer de sakta hai. Negative cycles mein toh infinite loop ho jayega.
• Negative weights ke liye Bellman-Ford algorithm use karo.
• Dijkstra BFS jaisa hai par priority queue use karta hai instead of normal queue.

Time Complexity

• Min-heap wala implementation: O((V + E) log V)
• Simple array wala: O(V�) � dense graphs ke liye thik hai
• Priority queue wala sabse efficient hai sparse graphs ke liye

Try it: code khud likho

Graph:
A: [(B,2), (C,5)]
B: [(C,1), (D,7)]
C: [(D,3)]
D: []

Common mistakes

• Negative weight graph par Dijkstra lagana � galat answer aayega. Bellman-Ford use karo.
• Heap se pop karne ke baad d > dist[node] check karna bhool jaana � redundant processing hogi.
• Weighted graph ki jagah unweighted graph par Dijkstra lagana � BFS enough hai.
• Priority queue mein (distance, node) ki jagah sirf node push karna � heap distance par sort nahi kar payega.