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).
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “Why does Dijkstra fail with negative edge weights?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Dijkstra relies on the greedy property: once a node is popped from the priority queue, its distance is final and optimal. This holds because all edge weights are non-negative — no future path can improve an already-settled distance. With negative edges, this assumption breaks: after settling node u with distance 5, a later path u -> v -> u with weight -10 could give distance -5 for u. Dijkstra would miss this improvement because u was already settled. Use Bellman-Ford for negative edges: it relaxes all edges V-1 times, allowing distances to improve through any path regardless of order. Note: negative edges are common in optimization problems (profit represented as negative cost), arbitrage detection, and resource allocation problems.”
}
},
{
“@type”: “Question”,
“name”: “How do you reconstruct the shortest path after running Dijkstra?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Track a prev (predecessor) array alongside the dist array. When updating dist[v] = dist[u] + w: also set prev[v] = u. After Dijkstra completes, reconstruct the path from source to target by following prev pointers backward: path = [target]. while prev[path[-1]] != source: path.append(prev[path[-1]]). path.append(source). Reverse the path. O(V) reconstruction. For the interview: always mention prev tracking when asked about path reconstruction. Edge case: if dist[target] is still INF after Dijkstra, no path exists. If prev[target] is None (never updated), the target is unreachable. Multiple shortest paths: Dijkstra finds one shortest path; finding all requires a modified DFS on the shortest path DAG.”
}
},
{
“@type”: “Question”,
“name”: “What is A* search and how does it differ from Dijkstra?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “A* adds a heuristic function h(n) to Dijkstra to guide the search toward the goal. Priority key: f(n) = g(n) + h(n) where g(n) = known shortest distance from source, h(n) = estimated remaining distance to goal. Dijkstra is A* with h(n)=0. A* expands nodes in order of f-value rather than g-value alone, preferring nodes that appear closer to the goal. This prunes nodes unlikely to be on the shortest path, often reducing nodes expanded by 10-100x. Requirement: h must be admissible (never overestimates) for guaranteed optimality. For grid problems: Manhattan distance (h = |dx| + |dy|) is admissible for 4-directional movement. Euclidean distance is admissible for any-direction movement. In interviews: mention A* when the graph is geometric and the goal is known (maze, map routing).”
}
},
{
“@type”: “Question”,
“name”: “When should you use Floyd-Warshall vs running Dijkstra from every vertex?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Floyd-Warshall: O(V^3) time, O(V^2) space. Simple 3-loop implementation. Handles negative edges (detects negative cycles). Use when: V is small (< 500), the graph is dense (E close to V^2), you need all-pairs distances. Running Dijkstra from every vertex: O(V*(V+E) log V). Use when: the graph is sparse (E <= 0 and node == dst: return cost. This modified Dijkstra explores in order of cost and tracks remaining stops. O(E*K log(E*K)) — works but is more memory-intensive than Bellman-Ford for this specific problem.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Uber Interview Guide