Choosing the Right Algorithm
Decision tree: non-negative weights? -> Dijkstra (O((V+E) log V)). Negative weights, no negative cycles? -> Bellman-Ford (O(V*E)). All-pairs shortest path? -> Floyd-Warshall (O(V^3)). Heuristic available (grid, geometric)? -> A* (faster than Dijkstra in practice). Unweighted graph? -> BFS (O(V+E)). DAG? -> DP in topological order (O(V+E)). For interviews: Dijkstra is the default for weighted graphs, BFS for unweighted.
Dijkstra Algorithm
Single-source shortest path with non-negative weights. Priority queue (min-heap) of (distance, node). Initialize dist[src]=0, all others=INF. While heap: pop (d, u). If d > dist[u]: stale entry, skip. For each neighbor v: if dist[u] + weight(u,v) < dist[v]: update dist[v], push (dist[v], v) to heap. O((V+E) log V) with a binary heap. Correctness: when a node is popped from the heap, its distance is finalized (greedy property holds for non-negative weights). Negative edges break this: a later path could improve an already-finalized distance.
import heapq
def dijkstra(graph, src):
dist = {node: float("inf") for node in graph}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return distBellman-Ford
Single-source shortest path with negative edges (but no negative cycles). Relax all edges V-1 times: for each edge (u,v,w): if dist[u]+w < dist[v]: dist[v] = dist[u]+w. After V-1 iterations, if any edge can still be relaxed: negative cycle exists. O(V*E) time. Use when: graph has negative weights, need to detect negative cycles, or the graph is sparse (otherwise Floyd-Warshall may be comparable). For dense graphs with negative weights: Bellman-Ford is often the only option. LC 743 Network Delay Time (Dijkstra if non-negative), LC 787 Cheapest Flights Within K Stops (Bellman-Ford variant with hop limit).
A* Search
A* extends Dijkstra with a heuristic function h(n) estimating the remaining distance to the goal. Priority: f(n) = g(n) + h(n) where g(n) = actual distance from source. Admissible heuristic: h(n) never overestimates the true distance (guarantees optimality). For grid problems: h = Manhattan distance (4-directional) or Euclidean distance. A* expands fewer nodes than Dijkstra by prioritizing nodes closer to the goal. Optimal when h is admissible. Identical to Dijkstra when h=0. Practical for: pathfinding in games, geographic routing (Google Maps uses A*-like algorithms). In interviews: mention A* when the graph has geometric structure and the goal is known upfront.
Floyd-Warshall
All-pairs shortest path. dp[i][j] = shortest distance from i to j. Initialize with edge weights (INF for no edge, 0 for self-loops). For each intermediate node k: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]). O(V^3) time, O(V^2) space. Detects negative cycles: if dp[i][i] < 0 after running. Use for: small dense graphs (V < 500), transitive closure, finding all-pairs distances in preprocessing. LC 1334 Find the City With the Smallest Number of Neighbors. Alternative for sparse graphs: run Dijkstra from every node — O(V*(V+E) log V), better when E << V^2.
Common Interview Patterns
- LC 743 Network Delay Time: Dijkstra from node k, answer is max of all distances.
- LC 787 Cheapest Flights Within K Stops: Bellman-Ford with K+1 relaxation rounds.
- LC 778 Swim in Rising Water: Dijkstra with cost = max elevation along path.
- LC 1631 Path With Minimum Effort: Dijkstra with cost = max absolute difference along path.
- LC 1514 Path with Maximum Probability: Dijkstra with max-heap (maximize product of probabilities).
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Uber Interview Guide