Dijkstra Interview Questions: Stale Heap Entries, Negative Edges, and Path Reconstruction

Dijkstra interview questions are proof questions disguised as heap questions. You keep the best tentative distance to every vertex, repeatedly select the smallest unsettled one, and relax its outgoing edges. The selection is safe only when edge weights are nonnegative: no future path through a farther vertex can return and improve the settled distance.

Dijkstra's 1959 paper is the primary source for the method. Princeton's technical API documents DijkstraSP for nonnegative weighted directed graphs. Python's heapq is a min-heap and does not provide a built-in decrease-key operation, so the clean Python interview implementation pushes a new pair after an improvement and skips stale pairs later.

Use Find Shortest Paths in Road Network as the closest PracHub drill while this guide develops the broader interview decision. PracHub question records are candidate-reported practice material: each record supports its own prompt, not a claim that every employer asks the same question.

Dijkstra Interview: Quick Answer

Initialize dist[source]=0, every other distance to infinity, and push (0,source). Pop (d,u); if d != dist[u], it is stale and must not drive relaxations. Otherwise, for each edge (u,v,w), reject w<0, compute candidate=d+w, and if it is smaller, update dist[v], set parent[v]=u, and push the new pair.

Early exit when the target is popped with d==dist[target]; discovery or push is too early because another unsettled route may improve it. Reconstruct by following parents from target to source and reversing. If the target distance is infinite, return the API's unreachable result. With a binary heap and adjacency lists, lazy duplicates give O((V+E) log V) in the conventional connected-case expression, often written O(E log V), and O(V+E) auxiliary storage including heap duplicates.

Prove the Settled-Distance Invariant

Suppose (d,u) is the valid minimum tentative pair. Assume a shorter path to u exists through an unsettled vertex. On that path, take the first unsettled vertex x; its predecessor is settled, so relaxation already assigned dist[x] no more than the path prefix. With nonnegative remaining edges, that prefix is no greater than the alleged shorter full path to u, hence less than d. That contradicts choosing u as the minimum.

The proof establishes finality at a valid pop, not at the first discovery. It also explains the negative-edge limit: a path can cross from a farther unsettled vertex through a negative edge and become shorter after u was settled. Stating the proof condition is more useful than memorizing “Dijkstra cannot do negatives.”

Skip Stale Heap Entries

Consider edges A→B=10, A→C=1, and C→B=2. Relaxing from A pushes (10,B) and (1,C). Popping C improves B to 3 and pushes (3,B). After (3,B) is processed, (10,B) remains in the heap. The check if d != dist[u]: continue discards it.

A separate visited set is valid if a node is marked only on its first valid minimum pop. Marking on push is wrong because B would be frozen at 10. The distance comparison is often simpler and tolerates multiple improvements. When floating weights are used, exact equality may be unsuitable; most coding prompts use integers, while production code needs a numeric contract.

Implement Distances and Parents Together

from heapq import heappop, heappush

def shortest_path(graph, source, target):
    dist = {v: float("inf") for v in graph}
    parent = {source: None}
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heappop(heap)
        if d != dist[u]:
            continue
        if u == target:
            break
        for v, w in graph[u]:
            if w < 0:
                raise ValueError("negative edge")
            nd = d + w
            if nd < dist[v]:
                dist[v], parent[v] = nd, u
                heappush(heap, (nd, v))
    if dist[target] == float("inf"):
        return float("inf"), []
    path, cur = [], target
    while cur is not None:
        path.append(cur); cur = parent[cur]
    return dist[target], path[::-1]

Require all referenced vertices to appear in the graph map or initialize them while reading edges. The strict improvement rule leaves the first equally short parent; add an explicit secondary policy only if canonical paths are required.

Reject Negative Edges with a Counterexample

Let S→A=2, S→B=5, and B→A=-10. Dijkstra pops A at distance 2 before B. But the path S→B→A costs -5. The earlier settlement is wrong because the negative edge erases the distance disadvantage of reaching B.

Bellman-Ford handles negative edges by repeatedly relaxing all edges and can detect a reachable negative cycle. On a directed acyclic graph, topological-order relaxation handles negative weights in linear time. If all weights are one, BFS is simpler. If weights are zero or one, a deque-based 0–1 BFS is appropriate. Choose from the weight domain rather than reaching for a heap automatically.

Validate the Reconstructed Path

Parent pointers update only when the matching distance improves. After reconstruction, verify the path begins at source, ends at target, every consecutive edge exists, and edge weights sum to the returned distance. This catches a bug where distance changes but parent does not, or where parent state from a previous run leaks into the result.

Multiple shortest paths require a tie contract. Keeping the first found is correct for distance but can depend on adjacency order. Lexicographically smallest full path cannot always be achieved by choosing the smallest immediate parent; it may need richer path comparison. Ask whether any shortest path is acceptable. Do not add expensive canonicalization when the prompt only needs one path.

State Early Exit and Multi-Source Variants

For one target, break at its valid pop. For many targets, continue until all requested targets have valid pops. For multi-source shortest distance, initialize every source to zero and push all of them; this is equivalent to adding a zero-cost super-source. Preserve which source won if the output needs ownership.

Bidirectional Dijkstra can reduce search for one source-target pair but adds stopping and reverse-graph details; do not introduce it before the baseline is correct. A* adds a heuristic and needs admissibility for optimality, plus consistency for the simplest settled behavior. These are follow-ups that change the proof, not cosmetic heap optimizations.

Test the Proof Conditions

Test one vertex, an unreachable target, parallel edges, a zero-weight edge, a cycle, the stale-entry graph, and a negative edge. For undirected input, insert both directions once and guard malformed self-loops according to the contract. Large path totals need a wide numeric type.

Compare distances against Bellman-Ford on small random nonnegative graphs. Validate each returned parent path independently. Heap-pop distances for valid entries should be nondecreasing. Every relaxed edge must satisfy dist[v] <= dist[u]+w at completion for reachable u; the shortest-path inequalities provide a useful oracle.

Do not test a particular pop order among equal distances unless the API requires it. Python heap tuples compare the second field on ties, so non-comparable vertex objects need a monotonic counter or wrapper. That is an implementation detail, not a shortest-path rule.

Make the Answer Reviewable

Turn the dijkstra design into a small deterministic review before adding more scale. Write the initial state, five to ten timestamped inputs, every expected state transition, and the exact read result at two watermarks. Replay one input, deliver another out of order, pause one consumer, and rebuild the serving view from its durable boundary. The replay should not create an extra effect, the stale input should follow the declared version rule, and the rebuilt read should match the authoritative result through the same watermark.

Keep expected results independent of the implementation. If the same code produces both the output and the assertion, a shared assumption can hide the defect. Add one invariant check that scans all state, even if production serves a faster index. For a distributed design, say which part this fixture does not prove: it does not measure production latency, network partitions, or capacity. Load and fault tests come next, using the traffic and error budgets already stated.

Finish with an operational table: signal, healthy range, action, and user-visible consequence. Include ingestion or queue age, rejected or duplicate work, authoritative-versus-serving divergence, and tail read latency. This makes the proposal inspectable. An interviewer can now change one requirement and see exactly which state, test, and alert must change with it.

Separate what the review establishes from what it leaves open. A passing deterministic fixture proves the declared state transitions for those inputs. It does not establish performance at scale, fairness across real users, or behavior during every network failure. Add a capacity test for the estimated peak, a skew test concentrated on one key or partition, and a fault test at the acknowledgment boundary. Record versions and random seeds so failures can be replayed. When a result differs from expectation, reduce it to the smallest trace, name the violated invariant, and repair that transition before retuning capacity. This evidence-first sequence keeps correctness questions from being hidden inside infrastructure changes.

Keep the review artifact beside the implementation and date the environment that produced it. If a later optimization changes ordering, batching, numeric width, or retry behavior, rerun the same trace before accepting the new result. The invariant is the stable comparison point; the component diagram is not.

Practice Five Related PracHub Questions

The first column links directly to five complete PracHub question records. Treat them as drills for transferable reasoning. They are candidate-reported practice evidence, not a forecast of a specific company interview.

A 45-Minute Interview Structure

Spend four minutes on graph direction, weight domain, output, and scale. Use six for the settlement proof. Code in twelve minutes, narrating the stale check and parent update. Trace the A-C-B example in six and the negative counterexample in five. Spend six on reconstruction and tests, four on complexity, and two on alternatives. If a negative edge appears, change algorithms immediately rather than patching visited behavior.

Final Takeaway

Dijkstra is correct because the smallest valid tentative distance cannot be improved through nonnegative remaining edges. A lazy Python heap may contain obsolete pairs; compare each pop with the current distance. Stop only when the target is validly popped, update parent with distance, and validate the final chain. Negative weights invalidate the proof and require a different algorithm.

Sources and Further Reading

• Dijkstra, A note on two problems in connexion with graphs
• Princeton DijkstraSP
• Princeton BellmanFordSP
• Python heapq

Research note: Technical documentation and linked PracHub practice records were checked on September 13, 2026. Documentation supports the stated system or algorithm behavior; individual question records support only their own practice contracts. Architecture recommendations and interview sequencing are editorial inference.