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.
{
“@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: when a node is popped from the min-heap, its shortest distance is finalized. This holds only if all edge weights are non-negative, because no future path can reduce the distance further (all paths get longer or stay the same as you add more edges). With a negative edge, a longer path through more nodes could be shorter than a direct path. Example: Au2192B costs 2, Au2192C costs 3, Cu2192B costs -2. Dijkstra finalizes dist[B]=2 when it pops B. But the path Au2192Cu2192B costs 1. The negative edge Cu2192B allows a cheaper path through a node processed after B. Bellman-Ford handles this by relaxing all edges V-1 times, not finalizing any distance until all rounds are complete.”
}
},
{
“@type”: “Question”,
“name”: “What is the time complexity of Dijkstra with a binary heap vs Fibonacci heap?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Binary heap (standard implementation): O((V+E) log V). Each vertex is pushed/popped at most once (V operations) and each edge relaxation may push to the heap (E operations). Each heap operation is O(log V). Fibonacci heap (theoretical): O(E + V log V). The decrease-key operation is O(1) amortized vs O(log V) for a binary heap. For dense graphs (E u2248 V^2), Fibonacci heap gives O(V^2 + V log V) = O(V^2) vs binary heap O(V^2 log V). For sparse graphs (E u2248 V), both give O(V log V). In practice, Fibonacci heaps have large constants and are rarely used. The lazy binary heap approach (push duplicates, skip stale entries on pop) gives the same O((V+E) log V) as a decrease-key heap but is simpler to implement and cache-friendly.”
}
},
{
“@type”: “Question”,
“name”: “How does BFS find the shortest path in an unweighted graph?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “BFS explores nodes in order of their distance from the source (measured in hops). All nodes at distance 1 are visited before nodes at distance 2, etc. When a node is first reached by BFS, that reach distance is the shortest path (it could not have been reached faster, since BFS already processed all closer nodes). Implementation: queue = deque([(start, 0)]); visited = {start}. Dequeue (node, dist), process neighbors: for each unvisited neighbor, mark visited, enqueue with dist+1. The first time the target is dequeued, dist is the answer. For reconstructing the path: store a parent dict. For grid problems (LC 1091 Shortest Path in Binary Matrix, LC 752 Open the Lock): treat each cell/state as a graph node and BFS over states. Time and space: O(V+E).”
}
},
{
“@type”: “Question”,
“name”: “When should you use Floyd-Warshall instead of running Dijkstra from every source?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Floyd-Warshall: O(V^3) time, O(V^2) space. Running Dijkstra from every source: O(V * (V+E) log V). For sparse graphs (E u2248 V): Dijkstra-all-pairs is O(V^2 log V) — faster than Floyd-Warshall O(V^3). For dense graphs (E u2248 V^2): Dijkstra-all-pairs is O(V^3 log V) — slower than Floyd-Warshall O(V^3). Use Floyd-Warshall when: the graph is dense, V is small (< 500 for practical run times), negative edges exist (Dijkstra cannot handle them; run Bellman-Ford from all sources instead). Floyd-Warshall also naturally handles negative edges (but not negative cycles). It is also simpler to code correctly for the all-pairs case. LC 1334: V=n cities, all-pairs needed for threshold check — Floyd-Warshall is the natural choice."
}
},
{
"@type": "Question",
"name": "How do you find the shortest path with at most K stops (LC 787)?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Modified Bellman-Ford: run exactly K+1 relaxation rounds (K stops means K+1 edges). Use two arrays: prev_dist (from previous round) and curr_dist (current round). For each round, relax all edges using prev_dist as the source — this prevents using edges from the same round (which would allow more than one hop per round). Return curr_dist[dst] after K+1 rounds. O(K*E) time. Dijkstra modification: extend the state to (cost, node, stops_remaining). Use a min-heap of (cost, node, k). When popping, if stops_remaining == 0 and node != dst, skip. This is valid because cost is non-negative (Dijkstra's guarantee holds for each (node, stops) state). O(K*E*log(K*V)) time. The Bellman-Ford approach is simpler for this specific problem."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide