Shortest Paths Coding Interview: Classify the Graph First
Learn how to classify a graph, choose the right shortest-path algorithm and state time and space complexity with confidence in a coding interview.
In a shortest paths coding interview, the questions are rarely a test of whether you memorised Dijkstra's code. They are a test of whether you can look at a graph, name its properties, and choose an algorithm you can defend. This article gives you a decision table, three worked examples and a script for stating complexity, so you practise the reasoning step that interviewers actually score.
The most useful habit you can build is to classify before you code. Say what kind of graph you have, say what kind of answer you need, then name the algorithm that fits. Everything below is arranged around that sequence.
Why Shortest Paths Coding Interview Questions Are Really Decision Questions
Interviewers usually care less about a flawless implementation than about the moment you decide. A candidate who says "let me check whether the weights can be negative" is showing something a memorised solution cannot: they know why the algorithm is correct.
Four questions settle almost every shortest-path problem:
- Are the edges weighted or unweighted?
- Can any edge weight be negative?
- Do I need one source, or distances between all pairs?
- Is this a general graph, or a grid with a fixed movement rule?
Ask these out loud in the first minute. A short narration works well: "The edges are unweighted, I need the distance from one start node, and it's a grid, so each move costs one. That points to breadth-first search." The interviewer can now follow you, and if you have misread the problem they can correct you before you write code.
One honest note: the goal is to demonstrate real reasoning, not to recite an answer you do not understand. If you are unsure whether an assumption holds, say so and ask. That is a stronger signal than confident guessing.
The Decision Table: Matching Graph Properties to Algorithms
This is the core of a shortest paths coding interview: a short table you can rebuild from memory and walk through out loud.
Unweighted, single source: BFS
When every edge costs the same, breadth-first search gives shortest paths in the number of edges. It is not merely the simpler option; it is correct because BFS explores nodes in order of distance from the source, so the first time you reach a node is via a shortest route.
Non-negative weights: Dijkstra
With a priority queue, Dijkstra repeatedly extracts the unvisited node with the smallest known distance. The intuition worth stating: because no edge can reduce a distance, the smallest tentative distance in the queue cannot be improved later, so it is final.
Negative weights: Bellman-Ford
Dijkstra's greedy step assumes distances only grow. A negative edge breaks that assumption. Bellman-Ford relaxes every edge repeatedly, which tolerates negative weights and can detect a negative cycle.
All pairs on a small dense graph: Floyd-Warshall
If you need every pair of distances and the node count is small, Floyd-Warshall's triple loop is cubic but simple. It is a trade-off, not a default. Repeated Dijkstra with a binary heap is O(V times (E + V) log V), which on a dense graph, where E is on the order of V squared, is O(V cubed log V). So Floyd-Warshall's O(V cubed) is asymptotically better as well as simpler, with a very small constant and no heap. Say that comparison rather than claiming one always wins.
DAGs: topological order plus relaxation
On a directed acyclic graph you can process nodes in topological order and relax each node's outgoing edges when you reach it, so every edge is relaxed exactly once. That handles negative weights and takes O(V + E) time overall, given a topological order, which itself costs O(V + E) to compute. That beats Dijkstra when the graph is acyclic. A clean example is a course-prerequisite graph where each edge carries a time credit or discount: one pass in prerequisite order settles every distance, even if some credits are negative.
General graph or grid?
The fourth question changes how you build the graph, not just which algorithm you pick. In a general graph you usually store an adjacency list and define V as the number of nodes and E as the number of edges. In a grid the edges are implicit: each cell has at most four neighbours, so you need no adjacency list, and V and E follow from the dimensions. Saying "V is rows times columns and E is at most about 4V, fewer since each edge is shared between two cells" shows you know why the same O(V + E) bound means something concrete here.
Say the choice out loud: "Because the weights are non-negative and I only need one source, Dijkstra is the natural fit." One sentence, and the interviewer knows your reasoning is deliberate.
Worked Example 1: BFS on an Unweighted Grid
Problem shape. A grid with obstacles. You start at one cell and want the fewest steps to a target cell, moving up, down, left or right.
Why BFS. Each move costs one, so distance equals the number of layers you have expanded. BFS visits all cells at distance 1, then all at distance 2, and so on. Depth-first search does not give shortest paths here: it commits to one route and can return a long way round even when a short one exists.
Walking through it without full code. Put the start cell in a queue and mark it visited. While the queue is not empty, take the front cell, look at its four neighbours, and for each neighbour that is inside the grid, not an obstacle and not yet visited, mark it visited and enqueue it. Track distance by processing the queue one level at a time: record the queue size at the start of each round, process exactly that many cells, then increment your step counter.
Complexity. O(V + E) time and O(V) space. For a grid with R rows and C columns, V is R times C and E is at most about 4V (fewer, since each edge is shared between two cells), so the bound is linear in the number of cells.
Common slip. Mark a cell visited when you enqueue it, not when you dequeue it. If you wait until dequeue, the same cell can be enqueued several times by different neighbours, which wastes work and can inflate your distance bookkeeping. Explain it as "marking on enqueue keeps each cell in the queue at most once."
Worked Example 2: Dijkstra on a Weighted Graph
Problem shape. Cities connected by roads with non-negative travel costs. Find the cheapest route from one city to another.
The invariant. Once a node is popped from the min-heap, its distance is final. The reason: the heap always offers the smallest tentative distance remaining, and since every edge weight is non-negative, no path through an unprocessed node can be shorter. Stating that invariant is often the whole point of the question.
Why the heap. A plain queue ignores weights and would give the wrong answer. A sorted list gives the right answer but makes each extraction expensive. A binary heap keeps extraction cheap, which is what you are paying the log factor for.
Complexity. O((V + E) log V) time with a binary heap. Space is O(V) for the distance array, plus the heap itself, which with lazy deletion can hold up to O(E) entries, so the lazy variant is O(V + E) space. The log factor is the cost of each heap operation, and you pay it once per node extracted and once per distance improvement.
Stale entries. When you improve a node's distance you push a new entry rather than updating the old one. Later you may pop an entry whose recorded distance is larger than the current best. Do not panic, and do not treat it as a bug: check whether the popped distance matches the stored distance, and if it does not, skip it. Say that out loud and the interviewer will see you understand the data structure.
Worked Example 3: Bellman-Ford and Negative Edges
Problem shape. A graph where some edges have a negative weight, for example a route where a leg gives a rebate that reduces total cost.
Why Dijkstra breaks. Picture three nodes: A to B costs 2, A to C costs 5, and C to B costs minus 4. Dijkstra finalises B at distance 2 before it ever considers the path through C, which would give 1. The greedy step assumed no later edge could improve a settled distance, and here one does.
How Bellman-Ford works. Relax every edge V minus 1 times. After each round, every shortest path using at most that many edges is correct. If a further round still improves some distance, the graph contains a negative cycle and shortest paths are not well defined.
Complexity. O(V times E) time and O(V) space. That is acceptable when the graph is small or when negative weights are genuinely part of the problem.
Even if you would reach for Dijkstra in practice, mentioning Bellman-Ford shows the interviewer you see the full decision space and know the boundary where your first choice stops working.
Stating Time and Space Complexity Without Hesitating
Define V and E out loud before you give a bound. Interviewers notice, and it prevents ambiguity when the same problem could be described as a grid or as a general graph.
Separate the cost of the algorithm from the cost of the data structure. Dijkstra is not inherently O((V + E) log V); that bound comes from choosing a binary heap. With an array-based scan it becomes quadratic. Naming the data structure makes the bound defensible.
A short script you can reuse:
- "The algorithm is Dijkstra."
- "The data structure is a binary min-heap."
- "That gives O((V + E) log V) time and O(V + E) space with lazy deletion, or O(V) if you decrease-key in place."
- "The log factor comes from heap operations: one extraction per node plus one push per distance improvement."
If you misspeak, do not freeze. Restate the assumption, then correct the bound: "Actually, I assumed a heap; with an array scan this would be O(V squared)." Recovering cleanly reads as competence, not as error.
Common Traps and How to Talk Through Them
Assuming non-negative weights. Check the problem statement before you commit. If it is silent, say what you are assuming and why it matters.
Using BFS on a weighted graph. BFS gives shortest paths only when every edge has equal weight. Otherwise it minimises edge count, not cost.
Confusing shortest path with minimum spanning tree. A shortest path connects one source to one target; a minimum spanning tree connects every node at minimum total cost. One line separates them: "I am optimising a route between two nodes, not the total wiring of the graph."
Overflow and unreachable nodes. Distances can exceed a 32-bit integer on large weighted graphs, so mention using a wider type. For unreachable nodes, return a sentinel such as infinity or minus one, and say which you chose.
A constraint added mid-problem. When the interviewer says "now some weights are negative", revisit your choice instead of defending it: "That breaks Dijkstra's invariant, so I would switch to Bellman-Ford or check whether the graph is a DAG." Adapting is the skill being tested.
A Practice Routine for Shortest-Path Questions
Practise classification separately from coding. Take ten shortest-path problems and spend two minutes on each doing nothing but naming the graph properties and the algorithm. No code. This isolates the step candidates usually skip, and it is the fastest way to improve at shortest paths coding interview questions.
Then run a weekly drill: five problems, ninety seconds each to classify the graph and name the algorithm, followed by the complexity script said aloud. No code, no notes. Record the session and review it against a short checklist: did you name V and E before the bound, did your justification match the properties you identified, and did you state the data structure alongside the complexity? If you said "Dijkstra" and then mentioned negative edges, that mismatch is what to fix next time.
Keep a one-page decision table you can reconstruct from memory rather than memorise verbatim. Four rows, five algorithms, one sentence of justification each. If you can rebuild it on a whiteboard, you can use it under pressure.
For a broader habit of explaining trade-offs rather than reciting solutions, our guide to Python Interview Questions: Concepts and Trade-Offs covers the same reasoning pattern in a different topic. You can find more practice-oriented writing on our blog.
Before You Walk In
Shortest-path questions reward the candidate who classifies first and codes second. Name the properties, name the algorithm, name the complexity, and let the interviewer watch you decide. Your next step: take five problems and spend ninety seconds on each saying the classification and the complexity script aloud, with no code. That single drill builds the habit that carries into the real thing.
Frequently asked questions
Which shortest-path algorithm should I use in a shortest paths coding interview?
Classify the graph first. Unweighted single-source points to BFS. Non-negative weights point to Dijkstra. Negative weights point to Bellman-Ford, or to topological order plus relaxation if the graph is a DAG. All-pairs distances on a small dense graph point to Floyd-Warshall. Say the properties you identified and then name the algorithm, so the choice sounds reasoned rather than recalled.
Can I use Dijkstra if the graph has negative edge weights?
No. Dijkstra finalises a node's distance when it is popped from the min-heap, which relies on every edge weight being non-negative. A negative edge can create a shorter route to a node you already settled, so the answer can be wrong. Use Bellman-Ford instead, or check whether the graph is acyclic and use topological order plus relaxation.
Do I need to implement a priority queue from scratch in an interview?
Usually you can use the language's built-in heap and say so. What matters is that you can explain what the heap buys you: cheap extraction of the smallest tentative distance, which is where the log factor in the time complexity comes from. If asked to implement one, a binary heap with sift-up and sift-down is the expected answer.
How do I explain the time complexity of Dijkstra without stumbling?
Give four parts in order: the algorithm, the data structure, the bound, and one sentence of justification. For example: Dijkstra with a binary min-heap runs in O((V + E) log V) time and O(V + E) space with lazy deletion, because heap operations cost a log factor, with one extraction per node plus one push per distance improvement. Naming the data structure is what makes the bound defensible.
What is the difference between shortest path and minimum spanning tree?
A shortest path minimises the cost of a route between a source and a target, or from one source to all nodes. A minimum spanning tree minimises the total cost of edges that connect every node together. They optimise different things, which is why Prim's and Kruskal's algorithms are not answers to a shortest-path question.
How do I practise shortest-path problems so the reasoning becomes automatic?
Separate classification from coding. Work through ten problems spending two minutes each on nothing but naming the graph properties and the algorithm, with no code. Then run a weekly drill of five problems, ninety seconds each to classify and name the algorithm, followed by the complexity script said aloud. Record it and check whether your stated reasoning matches the properties you identified. Keep a one-page decision table you can rebuild from memory.