Overview
Dijkstra algorithm weighted graph mein shortest path deta hai — GPS navigation ka base hai yaar.
Analogy
Jaise city mein sabse fast route dhundho — traffic ke hisaab se (edge weights) route choose karo.
Step-by-step
- Source node ke liye distance 0, baaki infinity
- Min-heap (priority queue) mein source add karo
- Heap se min distance node nikaalo
- Uske neighbors update karo agar shorter path mila
Visual
A->B=4, A->C=2, C->B=1
Dijkstra from A: dist[A]=0, dist[C]=2, dist[B]=3 (via C)
Common mistakes
- Negative weights pe kaam nahi karta — Bellman-Ford use karo
- Already visited node ko skip karo
- Heap pe duplicate entries — check current dist
Practice questions
- Dijkstra implement karo heapq se
- Cheapest flights within k stops solve karo