🎯 Graph Shortest Path
1️⃣ Core Framework
When discussing Graph Shortest Path, I frame it as:
- What shortest path problems are
- Graph representation
- BFS for unweighted shortest path
- Dijkstra for non-negative weighted graph
- Bellman-Ford for negative weights
- Floyd-Warshall for all-pairs shortest path
- 0-1 BFS
- Multi-source BFS
- Shortest path vs minimum spanning tree
- Senior-level explanation
2️⃣ What Problem Are We Solving?
Graph shortest path problems ask:
What is the minimum cost or minimum number of steps
to go from one node to another?
They are commonly used for:
- Shortest path in unweighted graph
- Shortest path in weighted graph
- Grid shortest path
- Minimum number of moves
- Network delay time
- Cheapest flights
- Word ladder
- Rotting oranges
- Walls and gates
- Path with minimum effort
- 0-1 weighted graph
- Negative weight detection
- All-pairs shortest path
The core idea is:
Graph shortest path finds the best route from source to target
based on edge count or edge weight.
👉 Interview Answer
Graph shortest path problems ask for the minimum distance or minimum cost between nodes.
If the graph is unweighted, BFS is usually the right tool.
If the graph has non-negative weights, Dijkstra is usually the standard solution.
If negative weights exist, Bellman-Ford may be needed.
If we need shortest paths between every pair of nodes, Floyd-Warshall is one option.
3️⃣ Graph Representation
Edge List
edges = [
[0, 1, 4],
[0, 2, 1],
[2, 1, 2]
]
Each edge means:
from node
to node
weight
Adjacency List
Most shortest path algorithms use adjacency list.
graph = {
0: [(1, 4), (2, 1)],
2: [(1, 2)]
}
Build Graph
from collections import defaultdict
def build_graph(edges):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
return graph
👉 Interview Answer
I usually represent graphs using an adjacency list.
For each node, the adjacency list stores its neighbors and edge weights.
This representation is efficient for graph traversal because we only visit outgoing edges from the current node.
4️⃣ Unweighted Shortest Path: BFS
When to Use BFS
Use BFS when:
all edges have the same cost
or
the graph is unweighted
Why?
BFS explores nodes by distance level.
distance 0
distance 1
distance 2
distance 3
The first time we reach a node, we have found the shortest number of edges to that node.
Code
from collections import deque
def shortest_path_unweighted(graph, start, target):
queue = deque([start])
distance = {start: 0}
while queue:
node = queue.popleft()
if node == target:
return distance[node]
for neighbor in graph[node]:
if neighbor not in distance:
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return -1
👉 Interview Answer
For an unweighted graph, BFS gives the shortest path in terms of number of edges.
BFS explores the graph level by level.
The first time a node is visited, that distance is guaranteed to be the shortest distance from the source.
5️⃣ BFS on Grid
Grid as Graph
A grid can be treated as a graph.
Each cell is a node.
Neighbors are usually:
up
down
left
right
Code
from collections import deque
def shortest_path_grid(grid):
rows = len(grid)
cols = len(grid[0])
queue = deque([(0, 0, 0)])
visited = set([(0, 0)])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
r, c, dist = queue.popleft()
if r == rows - 1 and c == cols - 1:
return dist
for dr, dc in directions:
nr = r + dr
nc = c + dc
if (
0 <= nr < rows
and 0 <= nc < cols
and grid[nr][nc] == 0
and (nr, nc) not in visited
):
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1
👉 Interview Answer
A grid shortest path problem can be modeled as an unweighted graph.
Each cell is a node, and valid neighboring cells are edges.
Since each move has the same cost, BFS finds the minimum number of moves.
6️⃣ Multi-Source BFS
When to Use Multi-Source BFS
Use multi-source BFS when there are multiple starting points.
Common examples:
Rotting Oranges
Walls and Gates
Nearest Exit
Distance to nearest zero
Map of highest peak
Key Idea
Put all starting nodes into the queue initially.
Then BFS expands from all sources at once.
Code
from collections import deque
def multi_source_bfs(grid, sources):
rows = len(grid)
cols = len(grid[0])
queue = deque()
distance = [[-1] * cols for _ in range(rows)]
for r, c in sources:
queue.append((r, c))
distance[r][c] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr = r + dr
nc = c + dc
if (
0 <= nr < rows
and 0 <= nc < cols
and distance[nr][nc] == -1
):
distance[nr][nc] = distance[r][c] + 1
queue.append((nr, nc))
return distance
👉 Interview Answer
Multi-source BFS starts BFS from all source nodes at the same time.
This is useful when we need the distance to the nearest source.
By pushing all sources into the queue with distance zero, BFS naturally expands in increasing distance order from the closest source.
7️⃣ Word Ladder
Problem
Transform one word into another word.
Each step can change one character.
All intermediate words must exist in the word list.
Why BFS?
Each transformation has equal cost.
So shortest transformation sequence is an unweighted shortest path problem.
Code
from collections import deque
def ladder_length(begin_word, end_word, word_list):
word_set = set(word_list)
if end_word not in word_set:
return 0
queue = deque([(begin_word, 1)])
visited = set([begin_word])
while queue:
word, steps = queue.popleft()
if word == end_word:
return steps
for i in range(len(word)):
for ch in "abcdefghijklmnopqrstuvwxyz":
next_word = word[:i] + ch + word[i + 1:]
if next_word in word_set and next_word not in visited:
visited.add(next_word)
queue.append((next_word, steps + 1))
return 0
👉 Interview Answer
Word Ladder is a shortest path problem on an implicit graph.
Each word is a node, and an edge exists if two words differ by one character.
Since every transformation has equal cost, BFS gives the shortest transformation length.
8️⃣ Weighted Shortest Path: Dijkstra
When to Use Dijkstra
Use Dijkstra when:
graph has non-negative edge weights
need shortest path from one source
Examples:
Network Delay Time
Path with Minimum Effort
Cheapest weighted path with no negative weight
Core Idea
Dijkstra always expands the node with the current smallest known distance.
Use a min heap:
(distance, node)
👉 Interview Answer
Dijkstra is used for shortest path in graphs with non-negative edge weights.
It uses a min heap to always process the node with the smallest known distance.
Once a node is finalized, its shortest distance from the source is known.
9️⃣ Dijkstra Template
Code
import heapq
from collections import defaultdict
def dijkstra(n, edges, source):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
distances = [float("inf")] * n
distances[source] = 0
heap = [(0, source)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distances
Important Detail
This line avoids processing stale heap entries:
if current_dist > distances[node]:
continue
👉 Interview Answer
My standard Dijkstra template uses an adjacency list, a distance array, and a min heap.
Whenever I find a shorter path to a neighbor, I update its distance and push it into the heap.
Since Python heap does not support decrease-key directly, stale entries may remain in the heap, so I skip them when popped.
🔟 Network Delay Time
Problem
Given directed weighted edges, return how long it takes for all nodes to receive a signal from source.
Dijkstra Idea
Run Dijkstra from source.
If all nodes are reachable, answer is the maximum shortest distance.
If some node is unreachable, return -1.
Code
import heapq
from collections import defaultdict
def network_delay_time(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
distances = [float("inf")] * (n + 1)
distances[k] = 0
heap = [(0, k)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
answer = max(distances[1:])
return answer if answer < float("inf") else -1
👉 Interview Answer
Network Delay Time is a single-source shortest path problem.
I run Dijkstra from the source node.
After computing shortest distances, the time for all nodes to receive the signal is the maximum distance.
If any node remains unreachable, I return -1.
1️⃣1️⃣ Path With Minimum Effort
Problem
Given a grid of heights, find a path from top-left to bottom-right minimizing the maximum absolute height difference along the path.
Why Dijkstra?
The path cost is not sum of edges.
It is:
maximum edge effort along the path
But the cost still never decreases as the path extends, so Dijkstra works.
Code
import heapq
def minimum_effort_path(heights):
rows = len(heights)
cols = len(heights[0])
efforts = [[float("inf")] * cols for _ in range(rows)]
efforts[0][0] = 0
heap = [(0, 0, 0)]
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while heap:
effort, r, c = heapq.heappop(heap)
if r == rows - 1 and c == cols - 1:
return effort
if effort > efforts[r][c]:
continue
for dr, dc in directions:
nr = r + dr
nc = c + dc
if 0 <= nr < rows and 0 <= nc < cols:
edge_effort = abs(heights[r][c] - heights[nr][nc])
new_effort = max(effort, edge_effort)
if new_effort < efforts[nr][nc]:
efforts[nr][nc] = new_effort
heapq.heappush(heap, (new_effort, nr, nc))
return 0
👉 Interview Answer
Path With Minimum Effort can be solved with Dijkstra.
The distance to a cell is the minimum possible maximum edge effort along a path.
When moving to a neighbor, the new path cost is the max of the current effort and the new edge effort.
Dijkstra works because this cost is non-decreasing as the path grows.
1️⃣2️⃣ 0-1 BFS
When to Use 0-1 BFS
Use 0-1 BFS when edge weights are only:
0 or 1
Instead of a heap, use a deque.
Key Idea
For weight 0 edge:
appendleft
For weight 1 edge:
append
This keeps nodes processed in increasing distance order.
Code
from collections import deque
def zero_one_bfs(n, graph, source):
distances = [float("inf")] * n
distances[source] = 0
deque_queue = deque([source])
while deque_queue:
node = deque_queue.popleft()
for neighbor, weight in graph[node]:
new_dist = distances[node] + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
if weight == 0:
deque_queue.appendleft(neighbor)
else:
deque_queue.append(neighbor)
return distances
👉 Interview Answer
0-1 BFS is used when all edge weights are either 0 or 1.
It uses a deque instead of a priority queue.
Weight 0 edges are pushed to the front, and weight 1 edges are pushed to the back.
This preserves increasing distance order more efficiently than Dijkstra.
1️⃣3️⃣ Bellman-Ford Algorithm
When to Use Bellman-Ford
Use Bellman-Ford when:
graph may contain negative edge weights
need single-source shortest path
need detect negative cycle
Core Idea
Relax all edges repeatedly.
For n nodes, shortest path without cycles has at most:
n - 1 edges
So we relax all edges:
n - 1 times
Code
def bellman_ford(n, edges, source):
distances = [float("inf")] * n
distances[source] = 0
for _ in range(n - 1):
updated = False
for u, v, w in edges:
if distances[u] != float("inf") and distances[u] + w < distances[v]:
distances[v] = distances[u] + w
updated = True
if not updated:
break
return distances
👉 Interview Answer
Bellman-Ford handles graphs with negative edge weights.
It relaxes every edge up to n - 1 times, because any shortest simple path can contain at most n - 1 edges.
It is slower than Dijkstra, but it can handle negative weights and detect negative cycles.
1️⃣4️⃣ Negative Cycle Detection
Key Idea
After relaxing edges n - 1 times,
try one more relaxation.
If any distance can still improve, there is a negative cycle reachable from the source.
Code
def has_negative_cycle(n, edges, source):
distances = [float("inf")] * n
distances[source] = 0
for _ in range(n - 1):
for u, v, w in edges:
if distances[u] != float("inf") and distances[u] + w < distances[v]:
distances[v] = distances[u] + w
for u, v, w in edges:
if distances[u] != float("inf") and distances[u] + w < distances[v]:
return True
return False
👉 Interview Answer
Bellman-Ford can detect negative cycles.
After n - 1 rounds of relaxation, shortest paths should already be finalized if no negative cycle exists.
If another relaxation can still improve a distance, that means a reachable negative cycle exists.
1️⃣5️⃣ Cheapest Flights Within K Stops
Problem
Find the cheapest price from source to destination with at most k stops.
Why Standard Dijkstra Is Tricky
The cheapest path so far may use too many stops.
State must include:
node
number of stops used
Bellman-Ford Style DP
Relax edges k + 1 times, because k stops means at most k + 1 edges.
Code
def find_cheapest_price(n, flights, src, dst, k):
prices = [float("inf")] * n
prices[src] = 0
for _ in range(k + 1):
next_prices = prices[:]
for u, v, price in flights:
if prices[u] == float("inf"):
continue
if prices[u] + price < next_prices[v]:
next_prices[v] = prices[u] + price
prices = next_prices
return prices[dst] if prices[dst] < float("inf") else -1
👉 Interview Answer
Cheapest Flights Within K Stops is a constrained shortest path problem.
I cannot only track the cheapest distance to each node, because the number of stops matters.
A clean solution is Bellman-Ford style DP: relax all edges k + 1 times, since k stops allows at most k + 1 edges.
1️⃣6️⃣ Floyd-Warshall Algorithm
When to Use Floyd-Warshall
Use Floyd-Warshall when:
need shortest path between all pairs of nodes
n is relatively small
Core Idea
Try every node as an intermediate node.
Transition:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Code
def floyd_warshall(n, edges):
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w)
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
Complexity
Time: O(n^3)
Space: O(n^2)
👉 Interview Answer
Floyd-Warshall computes shortest paths between all pairs of nodes.
It uses dynamic programming.
For each intermediate node k, it checks whether going from i to j through k gives a shorter path.
It is simple but O(n^3), so it is only practical when n is relatively small.
1️⃣7️⃣ Shortest Path in DAG
When Graph Is DAG
If the graph is a directed acyclic graph, we can compute shortest paths using topological order.
Idea
Process nodes in topological order.
Relax outgoing edges once.
Code
from collections import defaultdict, deque
def shortest_path_dag(n, edges, source):
graph = defaultdict(list)
indegree = [0] * n
for u, v, w in edges:
graph[u].append((v, w))
indegree[v] += 1
queue = deque()
for node in range(n):
if indegree[node] == 0:
queue.append(node)
topo = []
while queue:
node = queue.popleft()
topo.append(node)
for neighbor, weight in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
distances = [float("inf")] * n
distances[source] = 0
for node in topo:
if distances[node] == float("inf"):
continue
for neighbor, weight in graph[node]:
distances[neighbor] = min(
distances[neighbor],
distances[node] + weight
)
return distances
👉 Interview Answer
In a DAG, shortest path can be solved by processing nodes in topological order.
Because there are no cycles, each edge only needs to be relaxed once after its source node is finalized in topological order.
This works even with negative edge weights, as long as the graph is acyclic.
1️⃣8️⃣ BFS vs Dijkstra
BFS
Use when:
unweighted graph
all edges have equal cost
minimum number of steps
level-by-level traversal
Dijkstra
Use when:
weighted graph
all weights are non-negative
minimum cost path
edge costs differ
Comparison
| Pattern | Best For |
|---|---|
| BFS | Unweighted shortest path |
| Dijkstra | Non-negative weighted shortest path |
| 0-1 BFS | Edge weights are 0 or 1 |
| Bellman-Ford | Negative weights |
| Floyd-Warshall | All-pairs shortest paths |
👉 Interview Answer
BFS is the shortest path algorithm for unweighted graphs.
Dijkstra is for weighted graphs with non-negative weights.
If all edges have the same cost, using Dijkstra is unnecessary.
If edge weights differ, BFS is no longer correct unless the weights are only 0 and 1, where 0-1 BFS can be used.
1️⃣9️⃣ Shortest Path vs Minimum Spanning Tree
Shortest Path
Question:
What is the cheapest path from source to target?
Focus:
source-to-node distance
Algorithms:
BFS
Dijkstra
Bellman-Ford
Floyd-Warshall
Minimum Spanning Tree
Question:
How do we connect all nodes with minimum total edge weight?
Focus:
global connection cost
Algorithms:
Kruskal
Prim
Key Difference
Shortest path minimizes path cost from source.
MST minimizes total cost to connect all nodes.
They are not the same problem.
👉 Interview Answer
Shortest path and minimum spanning tree solve different problems.
Shortest path minimizes the cost from a source to a destination or to every node.
Minimum spanning tree minimizes the total cost required to connect all nodes.
An MST does not necessarily preserve shortest paths between nodes.
2️⃣0️⃣ Path Reconstruction
Problem
Sometimes we need the actual shortest path, not just the distance.
Idea
Store parent when updating distance.
parent[neighbor] = node
Then backtrack from target to source.
Code
import heapq
from collections import defaultdict
def dijkstra_path(n, edges, source, target):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
distances = [float("inf")] * n
parent = [-1] * n
distances[source] = 0
heap = [(0, source)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
parent[neighbor] = node
heapq.heappush(heap, (new_dist, neighbor))
if distances[target] == float("inf"):
return []
path = []
node = target
while node != -1:
path.append(node)
node = parent[node]
path.reverse()
return path
👉 Interview Answer
To reconstruct the shortest path, I store a parent pointer whenever I relax an edge and improve a distance.
After the algorithm finishes, I backtrack from the target through parent pointers until I reach the source.
Reversing that list gives the actual shortest path.
2️⃣1️⃣ Common Edge Cases
Unreachable Node
Distance remains:
infinity
Return:
-1
[]
or infinity
depending on the problem.
Source Equals Target
Shortest distance is:
0
Multiple Edges Between Same Nodes
Keep the smaller one or let relaxation handle it.
Directed vs Undirected
For undirected graph, add both directions:
graph[u].append((v, w))
graph[v].append((u, w))
Negative Weights
Dijkstra does not work with negative weights.
Use Bellman-Ford or DAG shortest path if applicable.
Cycles
Cycles are okay for BFS and Dijkstra as long as visited or distance logic prevents infinite loops.
👉 Interview Answer
Common shortest path edge cases include unreachable nodes, source equal to target, multiple edges between the same nodes, directed versus undirected edges, negative weights, and graph cycles.
The most important check is whether the graph is weighted and whether any weights are negative.
2️⃣2️⃣ Common Mistakes
Mistake 1: Using BFS on Weighted Graph
BFS only works when all edges have equal cost.
Mistake 2: Using Dijkstra With Negative Weights
Dijkstra assumes non-negative weights.
Mistake 3: Marking Visited Too Early in Dijkstra
In Dijkstra, a node may be pushed multiple times with better distances.
Use distance check:
if current_dist > distances[node]:
continue
Mistake 4: Forgetting 1-Indexed Nodes
Many graph problems use nodes:
1 to n
Distance array may need size:
n + 1
Mistake 5: Not Handling Unreachable Nodes
Distance may remain infinity.
Mistake 6: Confusing Stops and Edges
In flights problem:
k stops = k + 1 edges
👉 Interview Answer
Common shortest path mistakes include using BFS for weighted graphs, using Dijkstra with negative weights, marking nodes visited too early, mishandling 1-indexed nodes, forgetting unreachable nodes, and confusing stops with edges in constrained path problems.
2️⃣3️⃣ When Graph Shortest Path Applies
Good Fit
Use shortest path algorithms when the problem asks for:
minimum steps
minimum cost
least time
shortest route
minimum effort path
network delay
fewest transformations
distance from source
reach all nodes with minimum time
Problem Signals
Look for words like:
shortest
minimum
least
fewest
distance
steps
cost
time
route
path
effort
delay
👉 Interview Answer
I consider shortest path when the problem asks for minimum distance, minimum cost, minimum steps, minimum time, or least effort between states or nodes.
Then I decide the algorithm based on edge weights: BFS for unweighted, Dijkstra for non-negative weighted, Bellman-Ford for negative weights, and Floyd-Warshall for all-pairs shortest paths.
2️⃣4️⃣ When Graph Shortest Path Does Not Apply
Not Good Fit
Shortest path may not be ideal when:
need connected components only
need topological ordering
need minimum spanning tree
need cycle detection only
need all possible paths
need maximum flow
Better Alternatives
| Problem Type | Better Pattern |
|---|---|
| Connected components | DFS / BFS / Union Find |
| Dependency order | Topological Sort |
| Minimum total connection cost | MST / Kruskal / Prim |
| Cycle detection | DFS / Union Find |
| All possible paths | Backtracking / DFS |
| Dynamic connectivity | Union Find |
| Max flow | Ford-Fulkerson / Dinic |
👉 Interview Answer
Shortest path is not a general graph solution.
If the problem asks for connected components, topological order, cycle detection, or minimum spanning tree, other graph patterns are more appropriate.
The key is to identify whether the problem really asks for minimum route cost.
2️⃣5️⃣ Standard Templates
BFS Shortest Path Template
from collections import deque
def bfs_shortest_path(graph, source):
queue = deque([source])
distance = {source: 0}
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
Dijkstra Template
import heapq
from collections import defaultdict
def dijkstra(n, edges, source):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
distances = [float("inf")] * n
distances[source] = 0
heap = [(0, source)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distances
0-1 BFS Template
from collections import deque
def zero_one_bfs(n, graph, source):
distances = [float("inf")] * n
distances[source] = 0
queue = deque([source])
while queue:
node = queue.popleft()
for neighbor, weight in graph[node]:
new_dist = distances[node] + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
if weight == 0:
queue.appendleft(neighbor)
else:
queue.append(neighbor)
return distances
Bellman-Ford Template
def bellman_ford(n, edges, source):
distances = [float("inf")] * n
distances[source] = 0
for _ in range(n - 1):
updated = False
for u, v, w in edges:
if distances[u] != float("inf") and distances[u] + w < distances[v]:
distances[v] = distances[u] + w
updated = True
if not updated:
break
return distances
Floyd-Warshall Template
def floyd_warshall(n, edges):
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w)
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
🧠 Staff-Level Answer Final
👉 Interview Answer Full Version
Graph shortest path problems ask for the minimum distance, minimum cost, minimum time, or minimum number of steps between nodes or states.
The most important decision is whether the graph is unweighted or weighted.
If the graph is unweighted, BFS is the standard solution. BFS explores nodes level by level, so the first time we visit a node, we have found the shortest path in number of edges.
If the graph has non-negative edge weights, Dijkstra is usually the right algorithm. Dijkstra uses a min heap to always expand the node with the smallest known distance. When a shorter path to a neighbor is found, we update the distance and push it into the heap.
In Python, the heap may contain stale entries because there is no direct decrease-key operation. So I check whether the popped distance is greater than the best known distance, and skip it if it is stale.
If the graph has edge weights of only 0 and 1, 0-1 BFS can be more efficient than Dijkstra. It uses a deque: weight 0 edges go to the front, and weight 1 edges go to the back.
If the graph may contain negative weights, Dijkstra is not safe. Bellman-Ford can handle negative weights by relaxing all edges up to n - 1 times. It can also detect negative cycles by checking whether another relaxation is possible afterward.
If we need shortest paths between all pairs of nodes, Floyd-Warshall is a simple dynamic programming solution. It tries every node as an intermediate node, but it costs O(n^3), so it is only practical for smaller graphs.
For DAG shortest path, we can process nodes in topological order and relax each edge once. This can even handle negative edges, as long as there are no cycles.
Grid shortest path problems are graph problems too. Each cell is a node, and each valid move is an edge. If each move has equal cost, BFS is enough. If moving between cells has different cost, Dijkstra may be needed.
At a senior level, I would explain: how nodes and edges are modeled, whether edges are weighted, whether weights are negative, whether the graph is directed, whether we need one-source or all-pairs shortest path, and why the selected algorithm matches those constraints.
⭐ Final Insight
Graph Shortest Path 的核心不是“看到 graph 就 Dijkstra”。
它的核心是先判断 edge cost model：
unweighted 用 BFS， non-negative weighted 用 Dijkstra， 0/1 weights 用 0-1 BFS， negative weights 用 Bellman-Ford， all-pairs 用 Floyd-Warshall， DAG 可以用 topological order relaxation。
Senior-level 的重点是：
node 代表什么， edge 代表什么， weight 代表什么， source 和 target 是什么， 是否有 negative weights， 是否需要 path reconstruction， BFS 为什么适合 unweighted， Dijkstra 为什么要求 non-negative weights， 以及 shortest path 和 MST 为什么不是同一个问题。
能讲清楚这些， Graph Shortest Path 就是一类处理 minimum route、minimum cost、minimum time 和 minimum steps 的核心图算法模式。
中文部分
🎯 Graph Shortest Path
1️⃣ 核心框架
讨论 Graph Shortest Path 时，我通常从：
- Shortest path problems 是什么
- Graph representation
- BFS for unweighted shortest path
- Dijkstra for non-negative weighted graph
- Bellman-Ford for negative weights
- Floyd-Warshall for all-pairs shortest path
- 0-1 BFS
- Multi-source BFS
- Shortest path vs minimum spanning tree
- 高级工程师解释方式
2️⃣ 要解决什么问题？
Graph shortest path problems 问的是：
从一个 node 到另一个 node，
最小 cost 或最少 steps 是多少？
它常用于：
- Shortest path in unweighted graph
- Shortest path in weighted graph
- Grid shortest path
- Minimum number of moves
- Network delay time
- Cheapest flights
- Word ladder
- Rotting oranges
- Walls and gates
- Path with minimum effort
- 0-1 weighted graph
- Negative weight detection
- All-pairs shortest path
核心思想是：
Graph shortest path 根据 edge count 或 edge weight，
寻找从 source 到 target 的最佳路径。
👉 面试回答
Graph shortest path problems 是在图中寻找 nodes 之间的 minimum distance 或 minimum cost。
如果 graph 是 unweighted， BFS 通常是正确工具。
如果 graph 有 non-negative weights， Dijkstra 是标准解法。
如果存在 negative weights， 可能需要 Bellman-Ford。
如果需要所有 node pairs 之间的 shortest path， 可以考虑 Floyd-Warshall。
3️⃣ Graph Representation
Edge List
edges = [
[0, 1, 4],
[0, 2, 1],
[2, 1, 2]
]
每条 edge 表示：
from node
to node
weight
Adjacency List
大多数 shortest path algorithms 使用 adjacency list。
graph = {
0: [(1, 4), (2, 1)],
2: [(1, 2)]
}
Build Graph
from collections import defaultdict
def build_graph(edges):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
return graph
👉 面试回答
我通常用 adjacency list 表示 graph。
对每个 node， adjacency list 存它的 neighbors 和 edge weights。
这种表示方式适合 graph traversal， 因为我们只需要访问当前 node 的 outgoing edges。
4️⃣ Unweighted Shortest Path: BFS
When to Use BFS
当满足：
所有 edges cost 相同
或 graph 是 unweighted
使用 BFS。
为什么？
BFS 按 distance level 扩展 nodes：
distance 0
distance 1
distance 2
distance 3
第一次到达某个 node 时， 就找到了到它的最短 edge 数。
Code
from collections import deque
def shortest_path_unweighted(graph, start, target):
queue = deque([start])
distance = {start: 0}
while queue:
node = queue.popleft()
if node == target:
return distance[node]
for neighbor in graph[node]:
if neighbor not in distance:
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return -1
👉 面试回答
对 unweighted graph， BFS 可以求最短路径。
因为 BFS 是 level-by-level 扩展。
第一次访问到一个 node 时， 从 source 到这个 node 的距离一定是最短的。
5️⃣ BFS on Grid
Grid as Graph
Grid 可以看成 graph。
每个 cell 是一个 node。
Neighbors 通常是：
up
down
left
right
Code
from collections import deque
def shortest_path_grid(grid):
rows = len(grid)
cols = len(grid[0])
queue = deque([(0, 0, 0)])
visited = set([(0, 0)])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
r, c, dist = queue.popleft()
if r == rows - 1 and c == cols - 1:
return dist
for dr, dc in directions:
nr = r + dr
nc = c + dc
if (
0 <= nr < rows
and 0 <= nc < cols
and grid[nr][nc] == 0
and (nr, nc) not in visited
):
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1
👉 面试回答
Grid shortest path 可以建模成 unweighted graph。
每个 cell 是 node， 每个合法相邻 cell 之间有 edge。
因为每一步 cost 相同， BFS 可以找到 minimum number of moves。
6️⃣ Multi-Source BFS
When to Use Multi-Source BFS
当有多个起点时， 使用 multi-source BFS。
常见例子：
Rotting Oranges
Walls and Gates
Nearest Exit
Distance to nearest zero
Map of highest peak
Key Idea
一开始就把所有 source nodes 都放入 queue。
然后 BFS 从所有 sources 同时扩展。
Code
from collections import deque
def multi_source_bfs(grid, sources):
rows = len(grid)
cols = len(grid[0])
queue = deque()
distance = [[-1] * cols for _ in range(rows)]
for r, c in sources:
queue.append((r, c))
distance[r][c] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr = r + dr
nc = c + dc
if (
0 <= nr < rows
and 0 <= nc < cols
and distance[nr][nc] == -1
):
distance[nr][nc] = distance[r][c] + 1
queue.append((nr, nc))
return distance
👉 面试回答
Multi-source BFS 会从所有 source nodes 同时开始 BFS。
当我们需要求到最近 source 的距离时， 这个方法很有用。
把所有 sources 以 distance 0 放入 queue， BFS 会自然按照到最近 source 的距离逐层扩展。
7️⃣ Word Ladder
Problem
把一个 word 转换成另一个 word。
每一步只能改变一个 character。
所有中间 words 必须存在于 word list 中。
Why BFS?
每次 transformation cost 相同。
所以 shortest transformation sequence 是 unweighted shortest path problem。
Code
from collections import deque
def ladder_length(begin_word, end_word, word_list):
word_set = set(word_list)
if end_word not in word_set:
return 0
queue = deque([(begin_word, 1)])
visited = set([begin_word])
while queue:
word, steps = queue.popleft()
if word == end_word:
return steps
for i in range(len(word)):
for ch in "abcdefghijklmnopqrstuvwxyz":
next_word = word[:i] + ch + word[i + 1:]
if next_word in word_set and next_word not in visited:
visited.add(next_word)
queue.append((next_word, steps + 1))
return 0
👉 面试回答
Word Ladder 是 implicit graph 上的 shortest path problem。
每个 word 是一个 node。
如果两个 words 只差一个 character， 它们之间有一条 edge。
因为每次 transformation 的 cost 相同， BFS 可以求 shortest transformation length。
8️⃣ Weighted Shortest Path: Dijkstra
When to Use Dijkstra
当满足：
graph has non-negative edge weights
need shortest path from one source
使用 Dijkstra。
Examples:
Network Delay Time
Path with Minimum Effort
Cheapest weighted path with no negative weight
Core Idea
Dijkstra 每次扩展当前 known distance 最小的 node。
使用 min heap：
(distance, node)
👉 面试回答
Dijkstra 用于 non-negative edge weights 的 shortest path。
它使用 min heap， 每次处理当前 known distance 最小的 node。
当一个 node 被 finalized 后， 它从 source 出发的 shortest distance 就确定了。
9️⃣ Dijkstra Template
Code
import heapq
from collections import defaultdict
def dijkstra(n, edges, source):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
distances = [float("inf")] * n
distances[source] = 0
heap = [(0, source)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distances
Important Detail
这一行用来跳过 stale heap entries：
if current_dist > distances[node]:
continue
👉 面试回答
我的标准 Dijkstra 模板使用 adjacency list、 distance array 和 min heap。
当我找到到 neighbor 的更短路径时， 更新 distance， 并把新的 distance push 到 heap。
因为 Python heap 不支持直接 decrease-key， heap 中可能会有 stale entries， 所以 pop 出来时需要检查并跳过过期 entry。
🔟 Network Delay Time
Problem
给定 directed weighted edges， 返回 signal 从 source 传到所有 nodes 需要多久。
Dijkstra Idea
从 source 跑 Dijkstra。
如果所有 nodes 都 reachable， 答案是最大 shortest distance。
如果有 node unreachable， 返回 -1。
Code
import heapq
from collections import defaultdict
def network_delay_time(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
distances = [float("inf")] * (n + 1)
distances[k] = 0
heap = [(0, k)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
answer = max(distances[1:])
return answer if answer < float("inf") else -1
👉 面试回答
Network Delay Time 是 single-source shortest path problem。
我从 source node 开始跑 Dijkstra。
算出所有 shortest distances 后， signal 传到所有 nodes 的时间就是最大 distance。
如果有 node 仍然 unreachable， 返回 -1。
1️⃣1️⃣ Path With Minimum Effort
Problem
给定一个 heights grid， 从左上角到右下角找一条 path， 使得 path 上最大 height difference 最小。
Why Dijkstra?
Path cost 不是 edge sum。
而是：
path 上的 maximum edge effort
但是随着 path 扩展， cost 仍然不会下降， 所以 Dijkstra 仍然适用。
Code
import heapq
def minimum_effort_path(heights):
rows = len(heights)
cols = len(heights[0])
efforts = [[float("inf")] * cols for _ in range(rows)]
efforts[0][0] = 0
heap = [(0, 0, 0)]
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while heap:
effort, r, c = heapq.heappop(heap)
if r == rows - 1 and c == cols - 1:
return effort
if effort > efforts[r][c]:
continue
for dr, dc in directions:
nr = r + dr
nc = c + dc
if 0 <= nr < rows and 0 <= nc < cols:
edge_effort = abs(heights[r][c] - heights[nr][nc])
new_effort = max(effort, edge_effort)
if new_effort < efforts[nr][nc]:
efforts[nr][nc] = new_effort
heapq.heappush(heap, (new_effort, nr, nc))
return 0
👉 面试回答
Path With Minimum Effort 可以用 Dijkstra。
到达一个 cell 的 distance， 表示从起点到它的最小 possible maximum edge effort。
移动到 neighbor 时， new path cost 是 current effort 和 new edge effort 的最大值。
Dijkstra 适用， 因为这个 cost 随着 path 扩展是 non-decreasing 的。
1️⃣2️⃣ 0-1 BFS
When to Use 0-1 BFS
当 edge weights 只有：
0 or 1
时，可以使用 0-1 BFS。
不用 heap， 而是使用 deque。
Key Idea
对于 weight 0 edge：
appendleft
对于 weight 1 edge：
append
这样可以保持按照 increasing distance order 处理 nodes。
Code
from collections import deque
def zero_one_bfs(n, graph, source):
distances = [float("inf")] * n
distances[source] = 0
deque_queue = deque([source])
while deque_queue:
node = deque_queue.popleft()
for neighbor, weight in graph[node]:
new_dist = distances[node] + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
if weight == 0:
deque_queue.appendleft(neighbor)
else:
deque_queue.append(neighbor)
return distances
👉 面试回答
0-1 BFS 用于所有 edge weights 都是 0 或 1 的情况。
它使用 deque 代替 priority queue。
Weight 0 的 edge push 到 front， weight 1 的 edge push 到 back。
这样可以比 Dijkstra 更高效地保持 increasing distance order。
1️⃣3️⃣ Bellman-Ford Algorithm
When to Use Bellman-Ford
当满足：
graph may contain negative edge weights
need single-source shortest path
need detect negative cycle
使用 Bellman-Ford。
Core Idea
反复 relax 所有 edges。
对于 n 个 nodes， 没有 cycle 的 shortest path 最多包含：
n - 1 edges
所以 relax 所有 edges：
n - 1 times
Code
def bellman_ford(n, edges, source):
distances = [float("inf")] * n
distances[source] = 0
for _ in range(n - 1):
updated = False
for u, v, w in edges:
if distances[u] != float("inf") and distances[u] + w < distances[v]:
distances[v] = distances[u] + w
updated = True
if not updated:
break
return distances
👉 面试回答
Bellman-Ford 可以处理 negative edge weights。
它最多进行 n - 1 轮 edge relaxation， 因为任何 shortest simple path 最多包含 n - 1 条 edges。
它比 Dijkstra 慢， 但可以处理 negative weights， 并且可以检测 negative cycle。
1️⃣4️⃣ Negative Cycle Detection
Key Idea
在 relax edges n - 1 次后，
再尝试 relax 一次。
如果还有 distance 可以变小， 说明 source 可达范围内存在 negative cycle。
Code
def has_negative_cycle(n, edges, source):
distances = [float("inf")] * n
distances[source] = 0
for _ in range(n - 1):
for u, v, w in edges:
if distances[u] != float("inf") and distances[u] + w < distances[v]:
distances[v] = distances[u] + w
for u, v, w in edges:
if distances[u] != float("inf") and distances[u] + w < distances[v]:
return True
return False
👉 面试回答
Bellman-Ford 可以检测 negative cycle。
在 n - 1 轮 relaxation 后， 如果没有 negative cycle， shortest paths 应该已经稳定。
如果第 n 轮还可以继续改善某个 distance， 就说明存在 reachable negative cycle。
1️⃣5️⃣ Cheapest Flights Within K Stops
Problem
找从 source 到 destination 的最低价格， 并且最多允许 k stops。
Why Standard Dijkstra Is Tricky
当前最便宜 path 可能使用了太多 stops。
State 必须包括：
node
number of stops used
Bellman-Ford Style DP
Relax edges k + 1 次，
因为 k stops 表示最多 k + 1 条 edges。
Code
def find_cheapest_price(n, flights, src, dst, k):
prices = [float("inf")] * n
prices[src] = 0
for _ in range(k + 1):
next_prices = prices[:]
for u, v, price in flights:
if prices[u] == float("inf"):
continue
if prices[u] + price < next_prices[v]:
next_prices[v] = prices[u] + price
prices = next_prices
return prices[dst] if prices[dst] < float("inf") else -1
👉 面试回答
Cheapest Flights Within K Stops 是 constrained shortest path problem。
我不能只记录到每个 node 的最低价格， 因为 stops 数量也会影响答案。
一个清晰做法是 Bellman-Ford style DP： relax 所有 edges k + 1 次， 因为 k stops 最多允许 k + 1 条 edges。
1️⃣6️⃣ Floyd-Warshall Algorithm
When to Use Floyd-Warshall
当需要：
need shortest path between all pairs of nodes
n is relatively small
时，可以用 Floyd-Warshall。
Core Idea
尝试每个 node 作为 intermediate node。
Transition:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Code
def floyd_warshall(n, edges):
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w)
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
Complexity
Time: O(n^3)
Space: O(n^2)
👉 面试回答
Floyd-Warshall 用来计算 all-pairs shortest paths。
它使用 dynamic programming。
对每个 intermediate node k， 检查从 i 到 j 是否经过 k 会更短。
它实现简单， 但是 O(n^3)， 所以只适合 n 比较小的图。
1️⃣7️⃣ Shortest Path in DAG
When Graph Is DAG
如果 graph 是 directed acyclic graph， 可以用 topological order 计算 shortest paths。
Idea
按照 topological order 处理 nodes。
每条 outgoing edge 只 relax 一次。
Code
from collections import defaultdict, deque
def shortest_path_dag(n, edges, source):
graph = defaultdict(list)
indegree = [0] * n
for u, v, w in edges:
graph[u].append((v, w))
indegree[v] += 1
queue = deque()
for node in range(n):
if indegree[node] == 0:
queue.append(node)
topo = []
while queue:
node = queue.popleft()
topo.append(node)
for neighbor, weight in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
distances = [float("inf")] * n
distances[source] = 0
for node in topo:
if distances[node] == float("inf"):
continue
for neighbor, weight in graph[node]:
distances[neighbor] = min(
distances[neighbor],
distances[node] + weight
)
return distances
👉 面试回答
在 DAG 中， shortest path 可以通过 topological order 解决。
因为没有 cycles， 当一个 node 按 topological order 被处理时， 它之前的依赖已经处理过。
每条 edge 只需要 relax 一次。
即使 edge weight 是 negative， 只要 graph 是 acyclic， 这个方法仍然可以工作。
1️⃣8️⃣ BFS vs Dijkstra
BFS
适合：
unweighted graph
all edges have equal cost
minimum number of steps
level-by-level traversal
Dijkstra
适合：
weighted graph
all weights are non-negative
minimum cost path
edge costs differ
Comparison
| Pattern | Best For |
|---|---|
| BFS | Unweighted shortest path |
| Dijkstra | Non-negative weighted shortest path |
| 0-1 BFS | Edge weights are 0 or 1 |
| Bellman-Ford | Negative weights |
| Floyd-Warshall | All-pairs shortest paths |
👉 面试回答
BFS 是 unweighted graph 的 shortest path algorithm。
Dijkstra 用于 non-negative weighted graph。
如果所有 edges cost 相同， 没必要使用 Dijkstra。
如果 edge weights 不同， BFS 就不再正确， 除非 weights 只有 0 和 1， 这时可以使用 0-1 BFS。
1️⃣9️⃣ Shortest Path vs Minimum Spanning Tree
Shortest Path
问题是：
从 source 到 target 的最小 path cost 是多少？
关注：
source-to-node distance
Algorithms:
BFS
Dijkstra
Bellman-Ford
Floyd-Warshall
Minimum Spanning Tree
问题是：
如何用最小 total edge weight 连接所有 nodes？
关注：
global connection cost
Algorithms:
Kruskal
Prim
Key Difference
Shortest path 最小化 source 到 target 的 path cost。
MST 最小化连接所有 nodes 的 total cost。
它们不是同一个问题。
👉 面试回答
Shortest path 和 minimum spanning tree 解决的是不同问题。
Shortest path 最小化从 source 到 destination 的 cost， 或 source 到所有 nodes 的 cost。
Minimum spanning tree 最小化连接所有 nodes 所需的 total edge cost。
MST 不一定保留任意两个 nodes 之间的 shortest path。
2️⃣0️⃣ Path Reconstruction
Problem
有时我们不仅需要 distance， 还需要 actual shortest path。
Idea
每次更新 distance 时， 记录 parent：
parent[neighbor] = node
最后从 target 回溯到 source。
Code
import heapq
from collections import defaultdict
def dijkstra_path(n, edges, source, target):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
distances = [float("inf")] * n
parent = [-1] * n
distances[source] = 0
heap = [(0, source)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
parent[neighbor] = node
heapq.heappush(heap, (new_dist, neighbor))
if distances[target] == float("inf"):
return []
path = []
node = target
while node != -1:
path.append(node)
node = parent[node]
path.reverse()
return path
👉 面试回答
如果要 reconstruct shortest path， 我会在每次 relax edge 并更新 distance 时， 保存 parent pointer。
算法结束后， 从 target 沿着 parent pointers 一直回溯到 source。
最后 reverse 这个 list， 就得到 actual shortest path。
2️⃣1️⃣ 常见 Edge Cases
Unreachable Node
Distance 保持：
infinity
根据题目返回：
-1
[]
or infinity
Source Equals Target
Shortest distance 是：
0
Multiple Edges Between Same Nodes
可以保留更小的 edge， 也可以让 relaxation 自然处理。
Directed vs Undirected
对于 undirected graph， 要加双向边：
graph[u].append((v, w))
graph[v].append((u, w))
Negative Weights
Dijkstra 不适用于 negative weights。
要使用 Bellman-Ford， 或者如果是 DAG， 可以用 DAG shortest path。
Cycles
BFS 和 Dijkstra 都可以处理 cycles， 只要使用 visited 或 distance logic 防止无限循环。
👉 面试回答
Shortest path 常见 edge cases 包括 unreachable nodes、 source 等于 target、 multiple edges between same nodes、 directed vs undirected edges、 negative weights， 以及 graph cycles。
最重要的是判断 graph 是否 weighted， 以及 edge weights 是否可能为 negative。
2️⃣2️⃣ 常见错误
Mistake 1: Weighted Graph 中使用 BFS
BFS 只适用于所有 edges cost 相同的情况。
Mistake 2: Negative Weights 中使用 Dijkstra
Dijkstra 假设所有 weights non-negative。
Mistake 3: Dijkstra 中太早 Mark Visited
Dijkstra 中， 一个 node 可能以更好的 distance 被 push 多次。
使用 distance check：
if current_dist > distances[node]:
continue
Mistake 4: 忘记 1-Indexed Nodes
很多 graph problems 使用 nodes：
1 to n
Distance array 可能需要：
n + 1
Mistake 5: 没处理 Unreachable Nodes
Distance 可能一直是 infinity。
Mistake 6: 混淆 Stops 和 Edges
Flights problem 中：
k stops = k + 1 edges
👉 面试回答
Shortest path 常见错误包括： 在 weighted graph 中错误使用 BFS、 在 negative weights 中使用 Dijkstra、 在 Dijkstra 中过早 mark visited、 1-indexed nodes 处理错误、 忘记 unreachable nodes， 以及在 constrained path 中混淆 stops 和 edges。
2️⃣3️⃣ 什么时候 Graph Shortest Path 适用？
Good Fit
当题目问：
minimum steps
minimum cost
least time
shortest route
minimum effort path
network delay
fewest transformations
distance from source
reach all nodes with minimum time
Problem Signals
看到这些关键词想到 shortest path：
shortest
minimum
least
fewest
distance
steps
cost
time
route
path
effort
delay
👉 面试回答
当问题要求 minimum distance、minimum cost、 minimum steps、minimum time， 或 least effort between states/nodes 时， 我会考虑 shortest path。
然后根据 edge weights 决定算法： unweighted 用 BFS， non-negative weighted 用 Dijkstra， negative weights 用 Bellman-Ford， all-pairs shortest paths 用 Floyd-Warshall。
2️⃣4️⃣ 什么时候 Graph Shortest Path 不适用？
Not Good Fit
Shortest path 不一定适合：
need connected components only
need topological ordering
need minimum spanning tree
need cycle detection only
need all possible paths
need maximum flow
Better Alternatives
| Problem Type | Better Pattern |
|---|---|
| Connected components | DFS / BFS / Union Find |
| Dependency order | Topological Sort |
| Minimum total connection cost | MST / Kruskal / Prim |
| Cycle detection | DFS / Union Find |
| All possible paths | Backtracking / DFS |
| Dynamic connectivity | Union Find |
| Max flow | Ford-Fulkerson / Dinic |
👉 面试回答
Shortest path 不是通用 graph solution。
如果题目问 connected components、topological order、 cycle detection 或 minimum spanning tree， 其他 graph patterns 更合适。
关键是判断题目是否真的在问 minimum route cost。
2️⃣5️⃣ 标准模板
BFS Shortest Path Template
from collections import deque
def bfs_shortest_path(graph, source):
queue = deque([source])
distance = {source: 0}
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
Dijkstra Template
import heapq
from collections import defaultdict
def dijkstra(n, edges, source):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
distances = [float("inf")] * n
distances[source] = 0
heap = [(0, source)]
while heap:
current_dist, node = heapq.heappop(heap)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distances
0-1 BFS Template
from collections import deque
def zero_one_bfs(n, graph, source):
distances = [float("inf")] * n
distances[source] = 0
queue = deque([source])
while queue:
node = queue.popleft()
for neighbor, weight in graph[node]:
new_dist = distances[node] + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
if weight == 0:
queue.appendleft(neighbor)
else:
queue.append(neighbor)
return distances
Bellman-Ford Template
def bellman_ford(n, edges, source):
distances = [float("inf")] * n
distances[source] = 0
for _ in range(n - 1):
updated = False
for u, v, w in edges:
if distances[u] != float("inf") and distances[u] + w < distances[v]:
distances[v] = distances[u] + w
updated = True
if not updated:
break
return distances
Floyd-Warshall Template
def floyd_warshall(n, edges):
dist = [[float("inf")] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w)
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
🧠 Staff-Level Answer Final
👉 面试回答完整版本
Graph shortest path problems 是在 graph 或 state space 中寻找 minimum distance、 minimum cost、minimum time 或 minimum number of steps。
最重要的判断是 graph 是 unweighted 还是 weighted。
如果 graph 是 unweighted， BFS 是标准解法。 BFS 按 level-by-level 扩展 nodes， 所以第一次访问到某个 node 时， 就已经找到了最短 edge count。
如果 graph 有 non-negative edge weights， Dijkstra 通常是正确算法。 Dijkstra 使用 min heap， 每次扩展当前 known distance 最小的 node。 当找到到 neighbor 的更短路径时， 更新 distance 并 push 到 heap。
在 Python 中， heap 可能包含 stale entries， 因为没有直接 decrease-key 操作。 所以 pop 出 node 时， 如果 popped distance 大于已知 best distance， 就跳过。
如果 edge weights 只有 0 和 1， 0-1 BFS 通常比 Dijkstra 更高效。 它使用 deque： weight 0 edges 放到 front， weight 1 edges 放到 back。
如果 graph 可能有 negative weights， Dijkstra 不安全。 Bellman-Ford 可以通过最多 n - 1 轮 relax all edges 处理 negative weights。 它还可以通过额外一轮 relaxation 检测 negative cycle。
如果需要 all-pairs shortest path， Floyd-Warshall 是一个简单的 DP 解法。 它尝试每个 node 作为 intermediate node， 但复杂度是 O(n^3)， 所以只适合较小的 graph。
对 DAG shortest path， 可以按 topological order 处理 nodes， 每条 edge relax 一次。 这个方法甚至可以处理 negative edges， 前提是 graph 没有 cycle。
Grid shortest path 也是 graph problem。 每个 cell 是 node， 每个 valid move 是 edge。 如果每一步 cost 相同， BFS 就够了。 如果不同 move 有不同 cost， 可能需要 Dijkstra。
高级工程师解释 shortest path 时， 我会讲清楚： nodes 和 edges 如何建模， edges 是否 weighted， weights 是否可能 negative， graph 是否 directed， 是否需要 single-source 还是 all-pairs， 是否需要 path reconstruction， 以及为什么选择的 algorithm 符合这些 constraints。
⭐ Final Insight
Graph Shortest Path 的核心不是“看到 graph 就 Dijkstra”。
它的核心是先判断 edge cost model：
unweighted 用 BFS， non-negative weighted 用 Dijkstra， 0/1 weights 用 0-1 BFS， negative weights 用 Bellman-Ford， all-pairs 用 Floyd-Warshall， DAG 可以用 topological order relaxation。
Senior-level 的重点是：
node 代表什么， edge 代表什么， weight 代表什么， source 和 target 是什么， 是否有 negative weights， 是否需要 path reconstruction， BFS 为什么适合 unweighted， Dijkstra 为什么要求 non-negative weights， 以及 shortest path 和 MST 为什么不是同一个问题。
能讲清楚这些， Graph Shortest Path 就是一类处理 minimum route、minimum cost、minimum time 和 minimum steps 的核心图算法模式。
Implement