Shortest Path Algorithm Interview Patterns (2025)
Shortest path problems are fundamental in graph interviews. Knowing when to apply BFS, Dijkstra, Bellman-Ford, or Floyd-Warshall — and why each works or fails in specific scenarios — separates strong candidates.
Algorithm Selection Guide
| Scenario | Algorithm | Complexity |
|---|---|---|
| Unweighted graph | BFS | O(V + E) |
| Weighted, non-negative edges, single source | Dijkstra (min-heap) | O((V+E) log V) |
| Weighted, negative edges, single source | Bellman-Ford | O(V × E) |
| All-pairs shortest paths | Floyd-Warshall | O(V^3) |
| DAG (no cycles) | Topo sort + DP | O(V + E) |
| Grid (uniform cost) | BFS | O(rows × cols) |
| Grid (varying cost) | Dijkstra or A* | O(n log n) |
BFS for Unweighted Shortest Path
from collections import deque
def bfs_shortest_path(graph: dict, start, end) -> int:
"""Shortest path (in hops) from start to end. O(V + E)."""
if start == end:
return 0
visited = {start}
queue = deque([(start, 0)])
while queue:
node, dist = queue.popleft()
for neighbor in graph[node]:
if neighbor == end:
return dist + 1
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1 # Unreachable
def bfs_grid(grid: list[list[int]], start: tuple, end: tuple) -> int:
"""Shortest path in a 0/1 grid (0=open, 1=blocked). O(rows * cols)."""
rows, cols = len(grid), len(grid[0])
sr, sc = start
er, ec = end
if grid[sr][sc] == 1 or grid[er][ec] == 1:
return -1
visited = [[False] * cols for _ in range(rows)]
visited[sr][sc] = True
queue = deque([(sr, sc, 0)])
directions = [(0,1),(0,-1),(1,0),(-1,0)]
while queue:
r, c, dist = queue.popleft()
if r == er and c == ec:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and grid[nr][nc] == 0:
visited[nr][nc] = True
queue.append((nr, nc, dist + 1))
return -1Dijkstra’s Algorithm
import heapq
def dijkstra(n: int, edges: list[tuple], start: int) -> list[float]:
"""
Single-source shortest path for non-negative weighted graphs.
edges: list of (from, to, weight)
Returns distances from start to all nodes. O((V+E) log V).
"""
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((w, v))
adj[v].append((w, u)) # Remove for directed graph
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # Stale entry; skip
for weight, v in adj[u]:
new_dist = dist[u] + weight
if new_dist list[int]:
"""Returns the actual shortest path, not just distance."""
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((w, v))
adj[v].append((w, u))
dist = [float('inf')] * n
prev = [-1] * n
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for weight, v in adj[u]:
new_dist = dist[u] + weight
if new_dist int:
rows, cols = len(grid), len(grid[0])
dist = [[float('inf')] * cols for _ in range(rows)]
dist[start[0]][start[1]] = grid[start[0]][start[1]]
heap = [(grid[start[0]][start[1]], start[0], start[1])]
while heap:
cost, r, c = heapq.heappop(heap)
if (r, c) == end:
return cost
if cost > dist[r][c]:
continue
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
new_cost = cost + grid[nr][nc]
if new_cost < dist[nr][nc]:
dist[nr][nc] = new_cost
heapq.heappush(heap, (new_cost, nr, nc))
return -1Bellman-Ford (Handles Negative Edges)
def bellman_ford(n: int, edges: list[tuple], start: int) -> list[float]:
"""
Single-source shortest path with negative edges.
Detects negative cycles. O(V * E).
edges: list of (from, to, weight)
"""
dist = [float('inf')] * n
dist[start] = 0
# Relax all edges V-1 times
for _ in range(n - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break # Early termination if no updates
# Check for negative cycles (V-th relaxation still improves)
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w list[float]:
"""Average O(E), worst O(VE). Faster than BF in practice; same worst case."""
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w))
dist = [float('inf')] * n
dist[start] = 0
in_queue = [False] * n
in_queue[start] = True
queue = deque([start])
while queue:
u = queue.popleft()
in_queue[u] = False
for v, w in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if not in_queue[v]:
queue.append(v)
in_queue[v] = True
return distFloyd-Warshall (All-Pairs)
def floyd_warshall(n: int, edges: list[tuple]) -> list[list[float]]:
"""
All-pairs shortest paths. O(V^3) time, O(V^2) space.
Works with negative edges (but not negative cycles).
"""
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)
dist[v][u] = min(dist[v][u], w) # Remove for directed
for k in range(n): # Intermediate node
for i in range(n): # Source
for j in range(n): # Destination
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return distA* Search (Heuristic Shortest Path)
def a_star(grid: list[list[int]], start: tuple, end: tuple) -> int:
"""
A* with Manhattan distance heuristic for grid pathfinding.
Faster than Dijkstra when a good heuristic exists.
Admissible heuristic: h(n) g_score.get(pos, float('inf')):
continue
r, c = pos
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
new_g = g + 1
if new_g < g_score.get((nr, nc), float('inf')):
g_score[(nr, nc)] = new_g
heapq.heappush(heap, (new_g + heuristic((nr, nc)), new_g, (nr, nc)))
return -1Classic Interview Problems
def network_delay_time(times: list[list], n: int, k: int) -> int:
"""LeetCode 743: Time for signal to reach all nodes. Dijkstra."""
adj = [[] for _ in range(n + 1)]
for u, v, w in times:
adj[u].append((w, v))
dist = dijkstra_directed(n + 1, adj, k)
max_dist = max(d for i, d in enumerate(dist) if i != 0 and d != float('inf'))
return max_dist if max_dist != float('inf') else -1
def cheapest_flights(n: int, flights: list, src: int, dst: int, k: int) -> int:
"""LeetCode 787: Cheapest flight with at most k stops. Modified Bellman-Ford."""
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1): # k stops = k+1 edges
temp = dist[:]
for u, v, w in flights:
if dist[u] != float('inf') and dist[u] + w < temp[v]:
temp[v] = dist[u] + w
dist = temp
return dist[dst] if dist[dst] != float('inf') else -1Interview Tips
- Negative edges? Dijkstra fails — use Bellman-Ford. Dijkstra assumes once a node is finalized its distance is optimal; negative edges can improve a “finalized” node’s distance.
- Grid problems: BFS for unit weights; Dijkstra for variable-cost cells. A* if you need speed with a good heuristic (GPS navigation).
- K stops constraint: Modified Bellman-Ford with K iterations. Cannot use Dijkstra (it doesn’t bound the number of edges used).
- 0-1 BFS: Graph where edges have weight 0 or 1. Use deque — append front for 0-weight edges, append back for 1-weight edges. O(V + E) instead of O((V+E) log V).
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When should you use BFS vs Dijkstra vs Bellman-Ford for shortest path?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”BFS: use when all edge weights are equal (or unweighted). Runs in O(V+E) and guarantees shortest path by level. Dijkstra: use when all edge weights are non-negative. Runs in O((V+E) log V) with a min-heap. Cannot handle negative edges — a negative edge can make a “visited” node revisitable. Bellman-Ford: use when the graph may have negative edges. Runs in O(VE) — relax all edges V-1 times. Also detects negative cycles (a V-th relaxation that still improves means a negative cycle exists). Floyd-Warshall: use for all-pairs shortest paths with O(V^3) — practical only for dense graphs with V < 500."}},{"@type":"Question","name":"How does Dijkstra's algorithm work and why does it fail with negative edges?","acceptedAnswer":{"@type":"Answer","text":"Dijkstra uses a min-heap of (distance, node). Start with dist[source]=0, all others infinity. Each iteration: pop the minimum-distance node u, skip if already processed (stale heap entry). For each neighbor v, if dist[u] + weight(u,v) < dist[v], update dist[v] and push (dist[v], v) to the heap. Why negative edges break it: Dijkstra's correctness relies on the invariant that once a node is popped from the heap, its distance is final (greedy choice). A negative edge to an already-processed node could create a shorter path — but Dijkstra never revisits processed nodes, so it misses this. Bellman-Ford handles this by re-relaxing all edges V-1 times."}},{"@type":"Question","name":"How do you solve the cheapest flights problem (LeetCode 787) with Bellman-Ford?","acceptedAnswer":{"@type":"Answer","text":"LeetCode 787 asks for the cheapest price from src to dst with at most K stops. Use a constrained Bellman-Ford: run K+1 iterations (K stops = K+1 edges). At each iteration, only update costs using prices from the PREVIOUS iteration's dist array (use a copy). This prevents using more than one new edge per iteration. Time: O(K*E). The copy is critical — without it, a single iteration might chain multiple edges (buying more stops than allowed). Alternative: Dijkstra with state (node, stops_used) as the heap key, where the state space is O(V*K) and the algorithm is O(V*K * log(V*K))."}}]}
🏢 Asked at: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering
🏢 Asked at: Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering
🏢 Asked at: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture
🏢 Asked at: Coinbase Interview Guide
🏢 Asked at: Lyft Interview Guide 2026: Rideshare Engineering, Real-Time Dispatch, and Safety Systems