Choosing a shortest-path algorithm
“You are given a graph and asked for shortest paths. Walk me through how you choose the algorithm.”
What this tests
- Whether the candidate interrogates the graph before naming an algorithm.
- Precise knowledge of each algorithm's precondition and failure mode.
- Whether they know the cheaper special cases (BFS, 0-1 BFS) and do not over-engineer.
- Understanding of negative cycles, all-pairs vs single-source, and complexity in
VandE.
Strong answer
The algorithm is a function of the graph's properties, so the answer is a sequence of questions. Are edges weighted? If not, BFS Shortest Path (Unweighted) in O(V + E) — Dijkstra would be correct but strictly worse. Are all weights non-negative? Then Dijkstra's Algorithm with a binary heap, O((V + E) log V). Its greedy step — finalize the closest unfinalized node — is only valid because a path cannot get shorter by adding non-negative edges. Are there negative edges? Then Bellman-Ford, O(V · E), which relaxes all edges V - 1 times and can additionally detect a negative cycle with one more pass. Single source or all pairs? For all pairs on a dense graph, Floyd-Warshall is O(V^3) and trivial to write; on a sparse graph, running Dijkstra from every source is O(V (V + E) log V) and faster.
Then the special cases that save a log factor or more: weights only 0 and 1 → 0-1 BFS with a deque in O(V + E); a DAG (Directed Acyclic Graph) with arbitrary weights (including negative) → one pass in topological order, O(V + E); small integer weights bounded by W → Dial's buckets; a single target with a good heuristic → A* Search.
A strong candidate also notices constraint-shaped problems: "at most k stops" changes the state to (node, stops) and Bellman-Ford limited to k rounds is the natural fit, because Dijkstra's finalization does not respect the stop budget. And they say when the graph is implicit — grid cells, puzzle states — and how big V and E really are before committing.
Green flags · Red flags
- Asks about graph properties (weights, sign, cycles, density, source count) before naming anything.
- Does not immediately say Dijkstra; chooses BFS for unweighted graphs.
- Explains why Dijkstra's greedy finalization fails with negative edges, with a small example.
- Knows 0-1 BFS and DAG shortest path as strictly cheaper special cases.
- Gives complexities in
VandEand estimates them for the actual input size. - Recognizes that a budget constraint (
kstops) changes the state space and the algorithm. - Mentions negative cycle detection and what "shortest path" even means when one exists.
- Answers "Dijkstra" before asking anything.
- Uses Dijkstra with negative edges, or claims it works "if you allow re-insertion".
- Uses DFS for shortest paths on an unweighted graph.
- Cannot say what Floyd-Warshall's triple loop computes or why
kmust be the outer loop. - Does not know Bellman-Ford exists or its complexity.
- Gives complexity as
O(n log n)without definingn.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
k stops.10^5 nodes and 10^6 edges. Floyd-Warshall?