Chapter 34: DSA Dijkstra’s Algorithm
DSA Dijkstra’s Algorithm – Let’s learn this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing the graph step by step, explaining every single decision slowly, showing exactly what happens at each moment, and most importantly telling you why Dijkstra is one of the most frequently asked and most useful algorithms in interviews and real-world applications.
What is Dijkstra’s Algorithm?
Dijkstra’s algorithm finds the shortest path from a single source vertex to all other vertices (or to a specific target) in a graph with non-negative edge weights.
It was invented by Edsger W. Dijkstra in 1956 and remains one of the most important graph algorithms you will ever learn.
Key characteristics:
- Works only on graphs with non-negative edge weights
- Guarantees the shortest path (in terms of total weight)
- Uses a greedy strategy + priority queue
- Very commonly used in real life: GPS navigation, network routing, game AI, etc.
Real-life situations where Dijkstra is used
- Google Maps / Uber / Ola → shortest driving route
- Network routing protocols (OSPF) → lowest cost path
- Video game pathfinding (NPCs moving to player)
- Airline flight booking → cheapest flight route
- Social network → shortest chain of connections
- Resource allocation problems with costs
Core Idea of Dijkstra (very simple intuition)
Imagine you are standing at a starting point in a city and want to find the fastest way to reach every other place.
What would you do in real life?
- You start at your position → distance = 0
- You look at all direct roads from your position → note their distances
- You always choose to first explore the closest place you haven’t visited yet
- From there, you update distances to its neighbors if you find a better (shorter) path
- Repeat until you have visited all places
Dijkstra does exactly the same thing, but using math and a priority queue.
Important Rules of Dijkstra
- You can only relax (update) a distance if the new path is shorter
- You never revisit a node once its shortest distance is finalized
- You always pick the node with the current smallest known distance to explore next
- It works because edge weights are non-negative (no benefit in going through a negative edge later)
Classic Example Graph (we’ll solve step-by-step)
Vertices: A, B, C, D, E, F
Edges with weights:
- A → B : 4
- A → C : 2
- B → C : 1
- B → D : 5
- C → D : 8
- C → E : 10
- D → E : 2
- D → F : 6
- E → F : 3
Goal: Find shortest path from A to all other nodes (especially to F)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
4 5 A─────B─────D─────F │ 2 │ │ 6 └─────C─────┘ │ │ 8 │ 3 └─────E─────┘ 10 |
Step-by-step execution of Dijkstra (very detailed)
Initialize:
- dist[A] = 0
- dist[B,C,D,E,F] = ∞
- Priority queue (min-heap): [(0, A)]
- Previous (to reconstruct path): all None
Step 1 Extract min = A (dist = 0) Relax neighbors of A:
- B: 0 + 4 = 4 < ∞ → dist[B] = 4, previous[B] = A
- C: 0 + 2 = 2 < ∞ → dist[C] = 2, previous[C] = A
Queue now: (2, C), (4, B)
Step 2 Extract min = C (dist = 2) Relax neighbors of C:
- D: 2 + 8 = 10 < ∞ → dist[D] = 10, previous[D] = C
- E: 2 + 10 = 12 < ∞ → dist[E] = 12, previous[E] = C
Queue now: (4, B), (10, D), (12, E)
Step 3 Extract min = B (dist = 4) Relax neighbors of B:
- C: 4 + 1 = 5 > 2 → no update
- D: 4 + 5 = 9 < 10 → update dist[D] = 9, previous[D] = B
Queue now: (9, D), (12, E), (10, D) ← old one still there, but we ignore when we extract
Step 4 Extract min = D (dist = 9) Relax neighbors of D:
- E: 9 + 2 = 11 < 12 → update dist[E] = 11, previous[E] = D
- F: 9 + 6 = 15 < ∞ → dist[F] = 15, previous[F] = D
Queue now: (11, E), (12, E), (15, F)
Step 5 Extract min = E (dist = 11) Relax neighbors of E:
- F: 11 + 3 = 14 < 15 → update dist[F] = 14, previous[F] = E
Queue now: (14, F), (15, F)
Step 6 Extract min = F (dist = 14) No neighbors left → done
Final shortest distances from A:
- A: 0
- B: 4
- C: 2
- D: 9 (via A→B→D)
- E: 11 (via A→B→D→E)
- F: 14 (via A→B→D→E→F)
Shortest path to F: A → B → D → E → F (total cost = 14)
Dijkstra Code (standard interview version – priority queue)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
from heapq import heappush, heappop from collections import defaultdict def dijkstra(graph, start): # graph = {node: [(neighbor, weight), ...]} distances = defaultdict(lambda: float('inf')) distances[start] = 0 previous = {} pq = [(0, start)] # (distance, node) while pq: current_dist, node = heappop(pq) # Skip outdated entries if current_dist > distances[node]: continue for neighbor, weight in graph[node]: distance = current_dist + weight if distance < distances[neighbor]: distances[neighbor] = distance previous[neighbor] = node heappush(pq, (distance, neighbor)) return distances, previous |
To get path:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def reconstruct_path(previous, start, end): path = [] current = end while current is not None: path.append(current) current = previous.get(current) return path[::-1] if path and path[-1] == start else [] |
When to use Dijkstra (real decision guide)
| Situation | Best algorithm |
|---|---|
| All edges weight = 1 (unweighted) | BFS (faster & simpler) |
| Edges have non-negative weights | Dijkstra |
| Edges can have negative weights | Bellman-Ford |
| Need shortest path between all pairs | Floyd-Warshall (small V) |
| Graph has negative cycle | No algorithm gives correct answer |
Summary – Dijkstra’s Algorithm in one line each
- Finds single-source shortest paths in weighted graph
- Requires non-negative edge weights
- Uses greedy strategy + priority queue (min-heap)
- Time complexity: O((V + E) log V) with binary heap
- Space complexity: O(V)
- Most common shortest path algorithm in interviews and real-world applications
- One of the top 5 most important graph algorithms you must master
Would you like to go deeper into Dijkstra or related topics?
Very natural next steps:
- Step-by-step dry run of Dijkstra with priority queue changes
- Dijkstra vs Bellman-Ford detailed comparison
- Why Dijkstra fails with negative weights (visual proof)
- 0-1 BFS (special case when weights are 0 or 1)
- Shortest path in grid using Dijkstra
- How to reconstruct the actual path (using previous array)
Just tell me which one you want next — I’ll explain it in the same detailed, step-by-step, teacher style with clear examples and visuals! 😊
