1. One-Liner
Dijkstra grows a shortest-path tree from a source by always settling the not-yet-settled vertex with the smallest tentative distance (non-negative weights).
2. The Problem It Solves
Single-source shortest paths on a weighted graph where all edge weights ≥ 0. Applications: road networks, network routing, game maps with movement costs.
3. The Core Idea
Greedy correctness: the smallest tentative distance among unsettled nodes is final — no cheaper path can appear later if weights cannot be negative.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | dist[s]=0, others ∞; min-heap by (dist, vertex) |
| 2 | Pop vertex u with minimum dist; if stale, skip |
| 3 | For each edge (u,v,w): relax if dist[u]+w < dist[v] |
| 4 | Push updated (dist[v], v) |
| 5 | Repeat until heap empty or target reached (early exit) |
5. Dry Run Example
Nodes 0→1 weight 4, 0→2 weight 1, 2→1 weight 2. Start 0: dist [0,∞,∞] → relax 2: [0,∞,1] → settle 2 → relax 1: [0,3,1]. Shortest to 1 is 3 (via 2), not 4.
6. Key Properties
| Property | Value |
|---|---|
| Negative edges | Breaks algorithm — use Bellman-Ford |
| Implementation | Binary heap O((V+E) log V); Fibonacci heap O(E + V log V) |
| Dense graphs | Array + O(V²) variant sometimes simpler |
7. Where It Is Used
| System | Use |
|---|---|
| OSRM / routing engines | Road shortest paths |
| Network protocols | OSPF (conceptually related) |
| Games | Tile movement costs |
8. Interview Tips
Explain relaxation, why negative breaks, lazy deletion in heaps. Follow-ups: A*, bidirectional Dijkstra, k shortest paths.
9. Comparison with Other Algorithms
| Dijkstra | BFS | Bellman-Ford | |
|---|---|---|---|
| Weights | Non-neg | Unweighted / equal | Any (no neg cycle) |
| Time | (V+E)log V typical | O(V+E) | O(VE) |
10. Complexity
| -- | -- |
|---|---|
| Time | O((V + E) log V) with binary heap |
| Space | O(V + E) |
Implementation Example (PYTHON)
import heapq
def dijkstra(n, edges, src):
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
dist = [float('inf')] * n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d != dist[u]:
continue
for v, w in g[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist