Choosing the Right Algorithm
Unweighted graph (or all weights equal): BFS gives the shortest path in O(V+E). Weighted graph, non-negative weights: Dijkstra gives the shortest path in O((V+E) log V) with a min-heap. Weighted graph with negative edges (no negative cycles): Bellman-Ford in O(V*E). All-pairs shortest path: Floyd-Warshall in O(V^3). Weighted DAG (directed acyclic graph): topological sort + relaxation in O(V+E) — better than Dijkstra. Knowing which algorithm to apply requires recognizing the graph’s properties first.
Dijkstra’s Algorithm
Greedy shortest path for non-negative edge weights. Key insight: when a node is popped from the min-heap, its shortest distance is finalized (no shorter path exists because all remaining paths are at least as long as the current distance). Use a min-heap of (distance, node). Relax neighbors: if dist[u] + weight(u,v) < dist[v], update dist[v] and push to the heap.
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(heap, (dist[v], v))
return distThe stale-entry check (if d > dist[u]: continue) is critical for correctness when using a lazy-deletion heap (don’t update existing entries, just push new ones). O((V+E) log V) time. LC 743 (Network Delay Time), LC 1514 (Path with Maximum Probability), LC 787 (Cheapest Flights Within K Stops — modified Dijkstra with a hop limit).
Bellman-Ford Algorithm
Handles negative edge weights. Relaxes all edges V-1 times. After V-1 rounds: if any edge can still be relaxed, a negative cycle exists. O(V*E) time. Use when the graph has negative edges. Not needed for standard shortest path problems (Dijkstra is faster). LC 787 (Cheapest Flights, K stops) can also be solved with Bellman-Ford: run exactly K+1 relaxation rounds. Use two arrays (current and previous) to prevent using edges discovered in the same round.
BFS for Unweighted Shortest Path
Word Ladder (LC 127): transform word A to word B, changing one letter at a time, using only valid dictionary words. Model as a graph: each word is a node, edges connect words that differ by one letter. BFS from A; stop when B is reached. Optimization: instead of comparing all word pairs, use a wildcard pattern (h*t, *at, ha*) — group words by pattern. O(M^2 * N) where M = word length, N = dictionary size. Bidirectional BFS: run BFS from both A and B simultaneously; stop when frontiers meet. Reduces search space from O(b^d) to O(b^(d/2)).
Floyd-Warshall: All-Pairs Shortest Path
DP on all pairs through all possible intermediate nodes. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each intermediate node k. O(V^3) time. Use when you need shortest paths between all pairs and V is small (< 500). Detects negative cycles: after running, if dist[i][i] < 0 for any i, a negative cycle exists. LC 1334 (Find the City with Smallest Number of Neighbors at a Threshold Distance): Floyd-Warshall, then count reachable cities per node.
Topological Sort + DP for DAGs
For a DAG with weighted edges, process nodes in topological order and relax edges. Since there are no cycles, each node is processed after all its predecessors. O(V+E) — better than Dijkstra. Also works for longest path in a DAG (negate weights or use max instead of min). LC 1514 (maximum probability path) can be modeled as a DAG if the graph is a DAG. Critical Path Method (CPM) in project scheduling: longest path in a DAG of task dependencies gives the minimum project duration.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide