Now we move deeper into graphs.
The key interview question is:
Given a graph, how do I find the minimum-cost path from one node to another?
The correct algorithm depends mainly on edge weights.
1. First: Which Algorithm Should I Use?
Memorize this table:
| Graph | Algorithm |
|---|---|
| Unweighted graph | BFS |
Weights are only 0 and 1
|
0-1 BFS |
| Non-negative weights | Dijkstra |
| Negative weights possible | Bellman-Ford |
| All-pairs shortest paths | Floyd-Warshall |
| DAG | Topological-order shortest path |
Most important for interviews
Unweighted → BFS
Non-negative weighted → Dijkstra
Negative edges → Bellman-Ford
2. Unweighted Shortest Path
You already saw this with BFS.
Example:
0 --- 1 --- 2
|
3
Every edge has equal cost.
Starting from 0:
distance[0] = 0
distance[1] = 1
distance[2] = 2
distance[3] = 2
Use BFS:
from collections import deque
def shortest_path(graph, start):
distance = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in distance:
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return distance
Complexity
Time: O(V + E)
Space: O(V)
3. Why BFS Doesn't Work for Weighted Graphs
Consider:
A --10-- B
\ |
1 1
\ |
C---
There may be a path with more edges but lower total cost.
BFS minimizes:
number of edges
not:
total weight
For weighted graphs, we need another algorithm.
4. Dijkstra's Algorithm ⭐
Dijkstra finds shortest paths when:
All edge weights are non-negative.
Example:
4
A -------- B
| |
1| |2
| |
C -------- D
3
Starting from A:
A = 0
C = 1
B = 4
D = 4
5. Dijkstra's Core Idea
Maintain the best known distance to every node.
Initially:
start = 0
everything else = infinity
Then repeatedly:
- Pick the unprocessed node with the smallest distance.
- Examine its neighbors.
- Try to improve their distances.
This operation is called relaxation.
6. Relaxation
Suppose:
A --5--> B
and:
distance[A] = 3
Then the path through A costs:
3 + 5 = 8
If:
distance[B] = 10
we improve it:
distance[B] = 8
In code:
new_distance = distance + weight
if new_distance < dist[neighbor]:
dist[neighbor] = new_distance
This is the heart of Dijkstra.
7. Dijkstra Using heapq
Python's heapq is perfect for Dijkstra.
Graph format:
graph = {
0: [(1, 4), (2, 1)],
1: [(3, 1)],
2: [(1, 2), (3, 5)],
3: []
}
Each tuple means:
(neighbor, weight)
Implementation:
import heapq
def dijkstra(graph, start):
dist = {node: float("inf") for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > dist[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return dist
8. The Most Important Dijkstra Line
This line:
if current_dist > dist[node]:
continue
is extremely important.
Why?
heapq doesn't provide a direct decrease-key operation.
Instead, we may push multiple entries for the same node.
Example:
(10, B)
(7, B)
(5, B)
When (5, B) is processed, the old entries become stale.
So:
if current_dist > dist[node]:
continue
ignores them.
9. Dijkstra Complexity
Using an adjacency list + binary heap:
Time: O((V + E) log V)
Usually simplified to:
O(E log V)
Space:
O(V + E)
10. Dijkstra Cannot Handle Negative Weights
Example:
A --2--> B
A --5--> C
C --(-10)--> B
The path:
A → C → B
has cost:
5 + (-10) = -5
Negative edges can break Dijkstra's greedy assumption.
So:
Negative edge?
↓
Don't use Dijkstra
Use Bellman-Ford when appropriate.
11. Bellman-Ford
Bellman-Ford can handle:
- Positive edges
- Zero edges
- Negative edges
It can also detect negative cycles reachable from the source.
Basic Idea
Relax every edge repeatedly.
For V vertices, perform:
V - 1
passes.
Why V - 1?
A shortest simple path can contain at most V - 1 edges.
12. Bellman-Ford Implementation
Suppose:
edges = [
(0, 1, 4),
(0, 2, 5),
(1, 2, -3)
]
Each edge is:
(source, destination, weight)
Implementation:
def bellman_ford(n, edges, source):
dist = [float("inf")] * n
dist[source] = 0
for _ in range(n - 1):
changed = False
for u, v, weight in edges:
if dist[u] == float("inf"):
continue
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
changed = True
if not changed:
break
# Check for negative cycle
for u, v, weight in edges:
if dist[u] == float("inf"):
continue
if dist[u] + weight < dist[v]:
return None # Negative cycle
return dist
13. Bellman-Ford Complexity
Time: O(VE)
Space: O(V)
This is slower than Dijkstra for many normal weighted-graph problems.
So don't automatically use Bellman-Ford.
Use it when negative edges are relevant.
14. 0-1 BFS
What if every edge weight is either:
0 or 1
Example:
A --0--> B
B --1--> C
Instead of Dijkstra, we can use 0-1 BFS.
It uses a deque.
Rule
For an edge with weight 0:
appendleft()
For an edge with weight 1:
append()
Template
from collections import deque
def zero_one_bfs(graph, start, n):
dist = [float("inf")] * n
dist[start] = 0
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor, weight in graph[node]:
new_dist = dist[node] + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
if weight == 0:
queue.appendleft(neighbor)
else:
queue.append(neighbor)
return dist
Complexity:
O(V + E)
15. Floyd-Warshall
So far we've mostly found:
shortest paths from one source.
What if we want:
shortest paths between every pair of vertices?
Use Floyd-Warshall.
It uses dynamic programming.
Core idea
Let:
dist[i][j]
represent the shortest known distance from i to j.
For every intermediate node k:
dist[i][j] = min(
dist[i][j],
dist[i][k] + dist[k][j]
)
16. Floyd-Warshall Implementation
def floyd_warshall(dist):
n = len(dist)
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(
dist[i][j],
dist[i][k] + dist[k][j]
)
return dist
Complexity:
Time: O(V³)
Space: O(V²)
Therefore, it is usually appropriate for relatively small graphs.
17. Negative Cycle Detection with Floyd-Warshall
After running the algorithm:
for i in range(n):
if dist[i][i] < 0:
print("Negative cycle exists")
Why?
Normally:
dist[i][i] = 0
If it becomes negative, there is a negative-cost cycle reachable from i.
18. Dijkstra: Reconstruct the Actual Path
Sometimes the question doesn't ask only:
What is the shortest distance?
It asks:
What is the shortest path?
Maintain a parent array/dictionary.
import heapq
def dijkstra_with_path(graph, start, target):
dist = {node: float("inf") for node in graph}
parent = {node: None for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > dist[node]:
continue
if node == target:
break
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
parent[neighbor] = node
heapq.heappush(
heap,
(new_dist, neighbor)
)
if dist[target] == float("inf"):
return None
path = []
current = target
while current is not None:
path.append(current)
current = parent[current]
path.reverse()
return dist[target], path
For example:
A → C → D
could return:
(7, ["A", "C", "D"])
19. Important Problem: Network Delay Time
This is a classic Dijkstra problem.
You have:
times = [
[2, 1, 1],
[2, 3, 1],
[3, 4, 1]
]
Meaning:
2 → 1 with cost 1
2 → 3 with cost 1
3 → 4 with cost 1
Starting from node 2:
2 → 1 = 1
2 → 3 = 1
2 → 3 → 4 = 2
So the time needed for everyone to receive the signal is:
max(1, 1, 2) = 2
The pattern is:
Dijkstra
↓
shortest distance to every node
↓
take maximum distance
20. Important Problem: Cheapest Flights Within K Stops
This problem is trickier.
You have a limit:
maximum K stops
A normal Dijkstra implementation based only on the minimum cost per node can be insufficient because reaching a node cheaply with too many stops may not be a valid state.
The state becomes something like:
(cost, node, stops)
This teaches an important interview lesson:
Sometimes the graph state is more than just the node.
For example:
(node, remaining_steps)
(node, fuel)
(node, number_of_stops)
(node, time)
21. Shortest Path Recognition
This is extremely important.
Question says:
"Minimum number of edges"
Use:
BFS
Says:
"Minimum cost" with non-negative weights
Use:
Dijkstra
Says:
"Weights are 0 or 1"
Consider:
0-1 BFS
Says:
"Negative edge weights"
Use:
Bellman-Ford
Says:
"Shortest distance between every pair"
Consider:
Floyd-Warshall
Says:
"DAG"
Consider:
Topological-order shortest path
22. Dijkstra Template to Memorize ⭐
This is probably the most important code from today's topic:
import heapq
def dijkstra(graph, start):
dist = {node: float("inf") for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > dist[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(
heap,
(new_dist, neighbor)
)
return dist
Understand these three lines especially:
current_dist, node = heapq.heappop(heap)
new_dist = current_dist + weight
if new_dist < dist[neighbor]:
That's the core of Dijkstra.
23. Algorithm Comparison
| Algorithm | Weights | Main use | Time |
|---|---|---|---|
| BFS | Unweighted | Shortest path | O(V+E) |
| 0-1 BFS | 0/1 |
Shortest path | O(V+E) |
| Dijkstra | Non-negative | Single-source shortest path | O((V+E)log V) |
| Bellman-Ford | Can be negative | Single-source + negative cycle | O(VE) |
| Floyd-Warshall | Can be negative | All-pairs shortest path | O(V³) |
24. Common Interview Mistakes
❌ Using BFS on weighted edges
BFS minimizes the number of edges, not total cost.
❌ Using Dijkstra with negative weights
Dijkstra requires non-negative edge weights.
❌ Forgetting stale heap entries
Always consider:
if current_dist > dist[node]:
continue
❌ Confusing directed and undirected graphs
For an undirected edge:
graph[u].append((v, weight))
graph[v].append((u, weight))
For directed:
graph[u].append((v, weight))
❌ Returning only distance when path is required
Maintain:
parent[neighbor] = node
and reconstruct the path afterward.
25. Interview Practice
Easy
- Shortest path in an unweighted graph
- Network Delay Time
- Path With Minimum Effort
Medium
- Cheapest Flights Within K Stops
- Swim in Rising Water
- Minimum Cost to Connect Points
- 0-1 Matrix
- Minimum Obstacle Removal to Reach Corner
Advanced
- Bellman-Ford implementation
- Floyd-Warshall
- Cheapest Flights with state optimization
- Shortest Path Visiting All Nodes
🧠 Final Cheat Sheet
SHORTEST PATH
│
┌───────────┼───────────┐
│ │ │
Unweighted Weighted All pairs
│ │ │
BFS │ Floyd-Warshall
│
┌────────┼────────┐
│ │ │
0/1 Non-negative Negative
│ │ │
0-1 BFS Dijkstra Bellman-Ford
Next topic: Union-Find (Disjoint Set Union), Minimum Spanning Trees, Kruskal's and Prim's algorithms — another major interview/exam section.
Top comments (0)