Prompt and Scope
You are given a directed graph with n nodes labeled 0 through n - 1. Each edge is a tuple (from, to, weight). Given source and target, return a pair containing the shortest distance and one shortest path from source to target. Return (-1, []) when the target is unreachable.
For this version, assume 1 <= n <= 100000, 0 <= m <= 300000, every node label is valid, and 0 <= weight <= 10^9. Parallel edges, zero-weight edges, and self-loops are allowed. source and target are valid labels. If they are equal, return (0, [source]). Any shortest path is acceptable when several have the same distance.
For example, with edges (0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3), and (2, 4, 12), the answer from 0 to 4 is distance 7 and path [0, 2, 1, 3, 4].
The non-negative-weight condition is part of the algorithm contract. A weighted graph does not by itself imply Dijkstra: an unweighted graph favors BFS, a DAG can use topological dynamic programming, and a general graph with negative edges needs an algorithm such as Bellman-Ford.
What the Interviewer Evaluates
The first signal is algorithm selection from the contract. Dijkstra is suitable because edge weights are non-negative and only one source is involved. A candidate who says “weighted graph means Dijkstra” without asking about negative weights has missed the decisive precondition.
The second signal is the data structure invariant. An adjacency matrix would require O(V^2) space, which is unsuitable for up to 100,000 nodes. An adjacency list stores only the V + E information the traversal uses. A min-heap retrieves the unsettled node with the smallest discovered distance.
The third signal is how distance decreases are represented. Python's heapq does not update an arbitrary item in place. The practical solution pushes a new (distance, node) pair and later skips an old pair when its distance no longer equals distances[node]. This lazy-deletion detail is easy to omit and changes both correctness reasoning and the precise complexity bound.
The interviewer also expects a proof, not just working code. A strong answer explains why the first current entry popped for a node is final, why non-negative weights make that greedy step safe, and why the target may be returned when it is popped rather than when it is first discovered. Path reconstruction, unreachable input, zero-weight edges, parallel edges, integer width, and adversarial tests complete the answer.
Clarifying Questions Before Answering
- Can edge weights be negative? The base problem says no. If negative edges are allowed,
Dijkstra's settling proof and early exit do not hold.
- Is the graph directed? Yes. For an undirected graph, add both directions to the adjacency list.
- Do we need only the distance or also the path? This version needs both, so store a predecessor
whenever a relaxation strictly improves a distance.
- May there be parallel edges, zero-weight edges, or self-loops? Yes. The relaxation handles them
without preprocessing. A non-negative self-loop cannot improve its own node.
- What should unreachable mean? Return
(-1, []); do not confuse it with a zero-length path. - When several shortest paths exist, is any one acceptable? Yes. The implementation updates a
predecessor only on a strict improvement, so equal alternatives do not churn the path tree.
- How large can a distance become? A simple shortest path has at most
n - 1edges, so under the
stated bounds it is below 10^14. Python integers are unbounded; use a 64-bit integer in a fixed-width language.
30-Second Answer Framework
“I will build an adjacency list and keep distances[v], the best source-to-v distance found so far. I initialize the source to zero and put (0, source) in a min-heap. Each time I pop the smallest entry, I skip it if it is stale. Otherwise that node's distance is final because every remaining edge has non-negative weight. I relax each outgoing edge and push a new heap entry for every strict improvement, recording a predecessor for path reconstruction. I can stop when the target's current entry is popped. If its distance stays infinite, I return (-1, []); otherwise I follow predecessors backward and reverse the path. With lazy heap entries, time is O((V + E) log E) and space is O(V + E).”
Step-by-Step Deep Dive
Start by separating a discovered route from a proven shortest route. distances[v] is an upper bound on the true shortest distance because it is either infinity or the length of an actual route already found. Relaxing an edge u -> v with weight w tests whether the route through u is better: distances[u] + w < distances[v]. A strict improvement updates both the distance and previous[v].
The heap can contain several entries for the same node. In the example, edge 0 -> 1 first inserts distance 4. After node 2 is processed, route 0 -> 2 -> 1 improves node 1 to distance 3 and inserts a second entry. When (4, 1) is eventually popped, 4 != distances[1], so it is stale and must be ignored. No explicit heap-item deletion or node-visited set is required.
from heapq import heappop, heappush
def shortest_path(
n: int,
edges: list[tuple[int, int, int]],
source: int,
target: int,
) -> tuple[int, list[int]]:
graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for node, neighbor, weight in edges:
if weight < 0:
raise ValueError("Dijkstra requires non-negative edge weights")
graph[node].append((neighbor, weight))
distances = [float("inf")] * n
previous = [-1] * n
distances[source] = 0
heap: list[tuple[int, int]] = [(0, source)]
while heap:
distance, node = heappop(heap)
if distance != distances[node]:
continue
if node == target:
break
for neighbor, weight in graph[node]:
candidate = distance + weight
if candidate < distances[neighbor]:
distances[neighbor] = candidate
previous[neighbor] = node
heappush(heap, (candidate, neighbor))
if distances[target] == float("inf"):
return -1, []
path = []
node = target
while node != -1:
path.append(node)
node = previous[node]
path.reverse()
return int(distances[target]), pathThe correctness argument has two parts. First, every finite value in distances is the length of a real discovered path, so it cannot be smaller than the true shortest-path distance. Second, suppose a current entry for u is popped but there exists a shorter path to u. On that path, take the first node that has not yet been settled and call its predecessor x. Node x was settled earlier, so its outgoing edge was relaxed. The first unsettled node therefore received a heap key no greater than the length of the hypothetical shorter path to u. Because all remaining edge weights are non-negative, that key is smaller than the popped key for u and should have been popped first—a contradiction. Thus the popped current distance is final.
This proof also defines the safe early-exit point. Stop only after the target is popped with a current, non-stale distance. Do not stop when an edge first discovers the target: a later route may improve it. For the sample graph, the direct discovery of node 4 costs 13, while the final route costs 7.
previous[v] = u records the last edge of the currently best path to v. Once the target's distance is final, following predecessors must reach the source because each predecessor assignment came from a real source-rooted route. Reversing that chain returns the path in forward order. When source equals target, the source is popped immediately and reconstruction returns [source].
Building the adjacency list takes O(V + E) space and O(E) time. Each successful relaxation pushes one heap entry, so there are at most E such pushes in addition to the initial source entry. With lazy duplicates, the heap can contain O(E) entries, giving O((V + E) log E) time and O(V + E) total space. Textbooks often state O((V + E) log V) for a heap supporting decrease-key, or simplify to that bound for simple sparse graphs. Naming the lazy implementation's log E bound is more precise.
Test the contract, not only the happy path. The sample should return (7, [0, 2, 1, 3, 4]). Parallel edges and a zero weight—(0, 1, 10), (0, 1, 2), (1, 2, 0)—should return (2, [0, 1, 2]). Also test an unreachable target, source equal to target, a self-loop, equal-cost alternatives, and an edge of weight zero. A negative edge should raise the explicit error rather than silently produce an answer under a broken precondition.
A small differential test can generate non-negative graphs, run this function from every source, and compare its distances with Bellman-Ford. For returned paths, verify the first and last node, verify that every consecutive pair is an input edge, and sum the selected edge weights. With parallel edges, the test must associate the path step with a matching edge weight rather than assuming each node pair has one edge.
High-Quality Sample Answer
“I would first confirm that all edge weights are non-negative, the graph is directed, and any shortest path is acceptable. Those conditions let me use Dijkstra. I will store outgoing edges in an adjacency list because the graph can have 100,000 nodes and 300,000 edges; an adjacency matrix would be too large.
distances[v] starts at infinity except for the source, which starts at zero. A min-heap stores discovered (distance, node) pairs. When I find a shorter route through the current node, I update the neighbor's distance and predecessor and push a new pair. Since heapq has no arbitrary decrease-key, old pairs remain in the heap. I detect them by comparing the popped distance with the current array value and skip any mismatch.
The key proof is the settling invariant. When a current entry for node u is the heap minimum, any hypothetical shorter route would contain a first unsettled node whose predecessor was already settled. That predecessor's relaxation would have placed an equal or smaller prefix distance in the heap. Non-negative remaining weights mean that prefix should have been popped before u, which is a contradiction. Therefore u is final. This is why I may stop when the target's current entry is popped, but not when the target is first seen.
If the target remains infinite, I return (-1, []). Otherwise I follow predecessor pointers from the target to the source and reverse them. Each successful relaxation creates at most one new heap entry, so this lazy implementation runs in O((V + E) log E) time and uses O(V + E) space. In a fixed-width language I would use 64-bit distances. I would test stale entries, parallel and zero-weight edges, equal-cost paths, source equal to target, unreachable input, and rejection of a negative edge.”
Common Mistakes
- Running Dijkstra without asking about negative weights → the greedy finalization proof fails →
Make non-negative weights an explicit precondition and reject invalid input.
- Stopping when the target is first relaxed → the first discovered route may be expensive →
Stop only when the target's current heap entry is popped.
- Processing stale heap entries → old distances repeatedly scan outgoing edges → **Skip when
distance != distances[node].**
- Marking a node visited when it is first pushed → a later shorter route is suppressed → **A node
becomes settled only when its current minimum entry is popped.**
- Using an adjacency matrix → sparse input consumes
O(V^2)memory → **Use an adjacency list with
O(V + E) storage.**
- Updating predecessors on equal distances without a tie rule → zero-weight cycles can churn path
choices → Use strict improvement when any shortest path is acceptable.
- Returning a finite distance but no path contract → the implementation cannot satisfy the prompt
→ Record a predecessor on every strict improvement and reconstruct after the search.
- Calling this heap implementation
O(E log V)without qualification → lazy duplicates can make
the heap size proportional to E → **State O((V + E) log E), then explain the conventional decrease-key bound.**
- Using a 32-bit distance → paths can exceed about 2.1 billion → **Use Python integers or a 64-bit
type.**
- Testing only the final distance → a malformed predecessor chain goes unnoticed → **Validate
path endpoints, edges, and summed weight too.**
Follow-Ups and How to Handle Them
Follow-up 1: What changes if only the distance is required?
Remove the previous array and path reconstruction. The search, proof, and asymptotic bounds stay the same, although auxiliary node storage drops by one O(V) array. Early exit at the target's current pop remains safe.
Follow-up 2: What if we need shortest distances from every source?
Running Dijkstra from every node costs O(V(V + E) log E) with this implementation. For a dense graph, Floyd-Warshall uses O(V^3) time and O(V^2) space and also handles negative edges when there is no negative cycle. Johnson's algorithm combines reweighting with repeated Dijkstra for sparse graphs with negative edges but no negative cycles. Choose from the actual graph density and query volume.
Follow-up 3: What if negative edges are allowed?
Use Bellman-Ford for a general directed graph. It repeatedly relaxes all edges, runs in O(VE), and a further successful relaxation detects a reachable negative cycle. The counterexample 0 -> 1 = 2, 0 -> 2 = 5, 2 -> 1 = -10 shows the issue: early-exit Dijkstra settles target 1 at 2, but the true route through node 2 costs -5.
Follow-up 4: What if the graph is a DAG and some edges are negative?
Topologically sort the DAG, then relax outgoing edges once in topological order. Every predecessor is processed before its successor, so negative weights are safe and the total time is O(V + E). This beats Bellman-Ford and Dijkstra under the stronger acyclic contract.
Follow-up 5: What if every weight is either 0 or 1?
Use 0-1 BFS with a deque. Push a zero-weight relaxation to the front and a one-weight relaxation to the back. The deque preserves nondecreasing distance order, giving O(V + E) time without a heap.
Follow-up 6: How would frequent edge updates change the design?
For occasional updates, rebuild the adjacency list or change the affected edge and rerun Dijkstra; the simple solution is easiest to verify. Frequent updates with strict latency requirements call for dynamic shortest-path techniques or cached source trees with invalidation, whose value depends on update/query ratio and graph structure. Do not claim that a local edge change only affects its two endpoints.
Follow-up 7: How would you return the lexicographically smallest shortest path?
Strict distance comparison alone is insufficient because it deliberately keeps the first equal-cost path. Define the ordering contract first. One approach computes shortest distances, restricts candidate transitions to edges consistent with those distances, and then selects the smallest valid next node while ensuring the target remains reachable. Zero-weight cycles require cycle-aware handling. Comparing full path tuples inside every heap entry is simpler for small inputs but can add substantial copying and comparison cost.