skip to content

In lazy-deletion Dijkstra, what breaks if a vertex popped a second time is never skipped?

level: seniorimportance: nice to knowfreq 30%

answer

  1. ask what a duplicate entry can still do
  2. compare the stale key with the stored distance
  3. check whether the improvement test can ever fire
  4. count the adjacency scans, not the comparisons
  5. the harm is repeated work and heap size

basics

~20 s

Nothing breaks in the output: with non-negative weights the strict-improvement test rejects every update a stale pop could attempt. The damage is performance - each stale pop re-scans a settled vertex's whole adjacency list, and heap entries grow toward one per relaxation.

solid answer

~50 s

Lazy deletion means you never update a key in place: on every successful relaxation you push a fresh `(distance, vertex)` entry and let outdated ones sit in the heap. Those stale entries get popped later, after the vertex is already settled with a smaller distance. The standard guard is `if d > dist[u]: continue`. Without it, correctness still survives under non-negative weights: since `dist[u] <= d`, every edge out of `u` was already relaxed with the smaller value, so `d + w < dist[v]` can never hold. What you lose is work - each stale pop re-walks a settled vertex's adjacency list for nothing, so a high-degree hub gets rescanned repeatedly. Combined with a heap holding up to `E` entries rather than `V`, that is a real memory and latency problem at continental scale, and it hides in review because the output is still right.

code

pseudocode · 11 lines
pseudocode
// dist[] starts at infinity, dist[source] = 0
// Q holds (key, vertex) pairs; keys are never updated in place
heap_insert(Q, (0, source))
while Q is not empty:
    (d, u) = extract_min(Q)
    // nothing here compares d with dist[u]
    for each edge (u, v) with weight w:
        if d + w < dist[v]:
            dist[v] = d + w
            prev[v] = u
            heap_insert(Q, (d + w, v))

go deeper

for a junior

Know that some implementations push duplicate queue entries instead of updating keys, and that a vertex may therefore be popped more than once. The skip check is what makes that safe to ignore.

for a middle

Explain the two queue strategies and what each costs, and be able to say why the strict-improvement test already rejects a stale pop's updates when weights are non-negative.

for a senior

Review the code the way it will actually fail: name it a performance defect rather than crying correctness, quantify the redundant adjacency scans, and connect heap size to the graph's edge count.

for a principal

Weigh simplicity against the memory ceiling across a fleet: lazy deletion keeps the queue a commodity component, decrease-key bounds resident entries. Decide which cost the team can carry at the graph size you expect in two years.

## Two ways to keep the queue honest Dijkstra needs the frontier ordered by tentative distance, and tentative distances fall as relaxation proceeds. There are two ways to cope. **Decrease-key.** Keep at most one heap entry per vertex and lower its key in place when the distance improves. This needs the queue to know where each vertex currently lives inside it, which is extra machinery. **Lazy deletion.** Never update anything: on each successful relaxation, push a brand-new `(distance, vertex)` entry. Older entries for the same vertex remain in the heap as **stale** entries. When one is eventually popped, you notice the vertex is already settled and discard it. This is the version most implementations reach for because it needs nothing from the queue beyond push and pop-min. The entire correctness of lazy deletion rests on one line of code. ## The fragment under review The code example attached to this question is the lazy-deletion loop with that line missing. The reviewer's question is: is this a wrong-answer bug or a slow-code bug? ## The answer: it is a performance bug Under non-negative weights, no distance is corrupted. Here is the argument, and it is worth being able to give it precisely. Suppose `u` is popped with a stale key `d`, meaning `dist[u] < d`. The earlier, non-stale pop of `u` already relaxed every outgoing edge `(u, v)` using `dist[u]`, so at that moment `dist[v] <= dist[u] + w`. Distances never increase. Now the stale pop tests `d + w < dist[v]`. Since `dist[v] <= dist[u] + w < d + w`, the test is false for every neighbour. **No update fires.** The stale pop is pure waste. That is exactly why the missing guard survives review: the test suite passes, the routes are right, and nothing is visibly wrong. ## What the waste actually costs The cost is not one comparison. Every stale pop performs a **full scan of that vertex's adjacency list**, evaluating the relaxation test for every outgoing road. On a road graph, an intersection that lies on many cheap routes accumulates many heap entries, and each one buys a fresh sweep of its neighbours. In the worst case the number of heap entries is on the order of `E`, so the redundant scans are bounded by the sum of degrees over all stale pops rather than by `E` alone - the tidy `O((V + E) log V)` accounting quietly stops applying. Add the guard and the picture is clean again: at most `E` heap entries, each popped once at `O(log E) = O(log V)`, and at most `V` vertices actually expanded. ## The scale conversation This is where the reviewer's note turns into an architecture note. On a continental road graph of roughly `10^8` directed edges: - **Heap size.** Decrease-key caps the heap at `V` entries. Lazy deletion caps it at the number of successful relaxations, up to `E`. That is the difference between tens of millions and hundreds of millions of resident entries - a memory-ceiling question on every machine in the fleet, not a micro-optimization. - **Constant factors.** `log V` at `10^7` vertices is about 23, and `log E` about 27. The asymptotic difference is nothing; the difference in entries touched is everything. - **Where the time really goes.** At this size, cache behaviour dominates. Each stale pop touches an adjacency list that has long since fallen out of cache, so its cost is memory-bound, not comparison-bound. This is precisely the situation where profiling beats asymptotic reasoning. ## Reviewing it well The useful review comment is not "this is broken" - it is not. It is: *"this relies on the improvement test to neutralize stale pops, which works only while all weights are non-negative, and it pays a full adjacency scan per stale entry. Add the settled check; it is one line and it makes the invariant explicit rather than emergent."* The conditional in that sentence matters. If someone later introduces a negative weight into the cost model, the silent-but-correct property disappears along with everything else about the algorithm - the missing guard stops being a performance note and becomes one more way the output is wrong. A guard that states the invariant explicitly is cheaper than a guard that happens to be unnecessary today.

  • State the guard that belongs in that loop and prove it changes no output under non-negative weights.
    The guard is `if d > dist[u]: continue`, placed right after the pop. It changes no output because a stale pop cannot update anything anyway: `dist[u] <= d`, and every edge out of `u` was already relaxed with `dist[u]`, so `dist[v] <= dist[u] + w < d + w` and the strict-improvement test fails for every neighbour. The guard only skips work that would have been rejected.
  • At 10^8 edges, which resource does lazy deletion pressure first?
    Memory, through heap size. Decrease-key holds at most one entry per vertex; lazy deletion holds one per successful relaxation, so the queue can grow toward the edge count - hundreds of millions of entries instead of tens of millions. Latency follows, because each stale pop touches an adjacency list that has long since left cache, making the extra work memory-bound rather than comparison-bound.
  • Why do teams choose lazy deletion at all, if decrease-key bounds the heap so much better?
    Because it needs nothing from the priority queue beyond push and pop-min, so any plain min-heap works. Decrease-key requires the queue to track where each vertex currently sits inside it, which is extra structure to build, maintain and get right. Lazy deletion trades memory and some redundant pops for a much simpler component - usually the right trade until graph size makes the memory bill real.

saying these in an interview costs you the question

  • Claims stale pops corrupt already-settled distances
  • Says duplicate heap entries are completely harmless
  • Thinks the loop can fail to terminate
  • Cannot say why the improvement test rejects stale pops
  • Ignores that the heap now holds up to one entry per relaxation

context

resolving links…