Chapter 33: DSA Shortest Path
DSA Shortest Path – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing graphs step by step, explaining every algorithm slowly, comparing them side by side, showing multiple examples (with numbers and visuals), and most importantly telling you when to use which algorithm and why some algorithms are preferred in interviews.
What does “Shortest Path” actually mean?
In a graph, the shortest path problem asks:
Find the path from a source vertex to a destination vertex (or to all vertices) that has the minimum total edge weight.
Important variations:
- Single-source shortest path — from one source to all other vertices
- All-pairs shortest path — from every vertex to every other vertex
- Unweighted graph → all edges have weight 1 (or no weight)
- Weighted graph → edges have different costs (positive or negative)
The Four Most Important Shortest Path Algorithms (you must know these)
| Algorithm | Graph type | Edge weights | Negative weights? | Time Complexity | Best for |
|---|---|---|---|---|---|
| BFS | Unweighted / unit weight | All = 1 | No | O(V + E) | Unweighted graphs, shortest path in terms of number of edges |
| Dijkstra | Weighted | Non-negative | No | O((V + E) log V) with binary heap | Most common real-world weighted graphs |
| Bellman-Ford | Weighted | Can be negative | Yes (no negative cycle) | O(V × E) | Graphs with negative weights (but no negative cycle) |
| Floyd-Warshall | Weighted (all-pairs) | Can be negative | Yes (no negative cycle) | O(V³) | Dense graphs, all-pairs shortest path |
1. BFS – Shortest Path in Unweighted Graph
When to use BFS:
- All edges have same weight (usually 1)
- You want shortest path in terms of number of edges (not actual weight)
Key idea: BFS explores level by level → first time you reach a node, that is the shortest path (in terms of edges).
Example Graph (unweighted)
|
0 1 2 3 4 5 6 7 8 |
0 ── 1 ── 2 │ │ 3 ─────── 4 ── 5 |
Start from 0, find shortest path to 5.
BFS layers:
- Level 0: 0
- Level 1: 1, 3
- Level 2: 2, 4
- Level 3: 5
Shortest path length = 3 edges One possible path: 0 → 3 → 4 → 5
Code – BFS shortest path (unweighted)
|
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 |
from collections import deque def shortest_path_unweighted(graph, start, target): if start == target: return 0 visited = set() queue = deque([(start, 0)]) # (node, distance) visited.add(start) while queue: node, dist = queue.popleft() for neighbor in graph[node]: if neighbor not in visited: if neighbor == target: return dist + 1 visited.add(neighbor) queue.append((neighbor, dist + 1)) return -1 # no path |
2. Dijkstra’s Algorithm – Most Important for Weighted Graphs
When to use Dijkstra:
- Graph has non-negative edge weights
- You want shortest path in terms of actual cost (distance, time, money, etc.)
Key idea:
Always pick the closest unvisited node (smallest known distance) and relax all its neighbors.
Uses priority queue (min-heap) to always process the nearest node first.
Example Graph (weighted, non-negative)
|
0 1 2 3 4 5 6 7 8 9 10 11 |
4 0─────1 │ │ \ │ 2 │ 5 3─────2─────4 1 3 |
Start from 0, find shortest path to 4.
Step-by-step:
- Distance: 0→0 = 0, others = ∞
- Pick 0 (closest)
- Relax 1: dist[1] = 4
- Relax 3: dist[3] = 3
- Pick 3 (dist=3)
- Relax 2: dist[2] = 3 + 1 = 4
- Pick 1 (dist=4)
- Relax 2: 4 + 2 = 6 (worse than 4 → ignore)
- Relax 4: dist[4] = 4 + 5 = 9
- Pick 2 (dist=4)
- Relax 4: 4 + 3 = 7 (better than 9 → update)
- Pick 4 → done
Final distances: 0→4 = 7 Path: 0 → 3 → 2 → 4
Dijkstra Code (standard interview version)
|
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 |
from heapq import heappush, heappop def dijkstra(graph, start): distances = {node: float('inf') for node in graph} distances[start] = 0 pq = [(0, start)] # (distance, node) previous = {node: None for node in graph} while pq: current_dist, node = heappop(pq) 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 reconstruct path:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
def get_path(previous, start, end): path = [] current = end while current is not None: path.append(current) current = previous[current] return path[::-1] if path[-1] == start else [] |
3. Bellman-Ford – Handles Negative Weights
When to use Bellman-Ford:
- Graph has negative edge weights
- But no negative-weight cycle reachable from source
Key idea:
Relax all edges |V|-1 times → after that, every shortest path is found.
If another relaxation is possible → negative cycle exists.
Summary – Shortest Path Algorithms Cheat Sheet
| Algorithm | Edge weights | Negative edges? | Negative cycle? | Time Complexity | Best use case |
|---|---|---|---|---|---|
| BFS | Unweighted / unit | No | No | O(V + E) | Number of edges shortest path |
| Dijkstra | Non-negative | No | No | O((V+E) log V) | Most weighted graphs (roads, networks) |
| Bellman-Ford | Any | Yes | Detects | O(V × E) | Negative weights allowed |
| Floyd-Warshall | Any | Yes | Detects | O(V³) | All-pairs, dense graphs, small V |
Would you like to go deeper into any specific shortest path topic?
Very common follow-up topics:
- Dijkstra step-by-step dry run with priority queue
- Bellman-Ford – how it detects negative cycle
- Floyd-Warshall – all-pairs shortest path
- Shortest path in grid (BFS vs Dijkstra)
- 0-1 BFS (special case when weights are 0 or 1)
- Difference between Dijkstra vs Bellman-Ford (very common interview question)
Just tell me which one you want next — I’ll explain it with the same level of detail, visuals, and step-by-step clarity! 😊
