Question 1

Where does the log factor in O((V + E) log V) come from? Not what — where.

Accepted Answer

From the heap: every push and pop costs log of the heap size, and there is one per relaxation. Strip the heap out and Dijkstra is V pops and E relaxations, which is linear. The logarithm is entirely the price of repeatedly asking "which unsettled node is cheapest", and a binary heap charges log of its size for both the push and the pop. That is also why the bound moves: a Fibonacci heap makes decrease-key O(1) amortized and gives O(E + V log V), and on a dense graph a plain array scan gives O(V²), which is better still.

Question 2

On a dense graph with E close to V², is the binary heap still the right structure?

Accepted Answer

No — a linear scan for the minimum gives O(V²), which beats O(V² log V) when E is that large. The heap costs (V + E) log V; the classic no-heap version scans all V tentative distances on each of V settles, for V² total, plus O(E) relaxations. When E is already V², the scan version is O(V²) and the heap version carries a log V multiplier on top of the same work. Knowing when *not* to pay for the priority queue is as much part of the algorithm as the queue itself.

Question 3

With lazy deletion the heap can hold more than V entries. How many nodes actually get settled?

Accepted Answer

Exactly one per reachable node — later pops of the same node hit the settled check and are skipped. The heap is allowed to grow to O(E) entries because pushing a duplicate is cheaper than reaching into the heap to fix an old one. What keeps the algorithm linear in settles is the two-line guard at pop: if the node is already settled, discard the entry and continue. The trace narrates that skip when it happens, so you can see one stale entry surface rather than take the technique on trust.

Question 4

Why is it safe to declare the smallest tentative distance final, before exploring the rest?

Accepted Answer

Any rival route must leave through an unsettled node whose label is already at least as large, plus non-negative edges. Suppose node `u` is about to settle at `d` but a cheaper path exists. That path must cross from the settled region into the unsettled one at some node `v`, and `v`’s tentative label is at least `d` or it would have been chosen instead. The rest of the path adds non-negative weight, so the total is at least `d` — a contradiction, and the whole proof turns on that one non-negativity step.

Question 5

Now one edge has weight −2. What does Dijkstra do?

Accepted Answer

It finishes normally and returns wrong distances, because a settled node is never reconsidered. A negative edge lets a route get cheaper as it goes, so the claim "nothing beyond the frontier can undercut this" fails — but no line of code ever checks. Nodes settle, the loop ends, and plausible numbers come out. The remedy is a different algorithm: Bellman–Ford at O(VE), which also reports negative cycles, or Johnson’s reweighting when you need all pairs.

Question 6

Bellman–Ford handles negative weights. Why not use it everywhere and skip the precondition?

Accepted Answer

It costs O(VE) rather than O((V + E) log V) — orders of magnitude more on the graphs people actually run. Bellman–Ford relaxes every edge V − 1 times because it has no safe order to relax them in; Dijkstra’s greedy choice is exactly the trick that makes one pass per node enough. On a road network with a million nodes that difference is minutes against milliseconds. Pay the O(VE) only when negative weights are genuinely possible — and then you also get negative-cycle detection, which Dijkstra cannot offer at any price.

Question 7

What property of the settle sequence would immediately reveal a broken implementation?

Accepted Answer

A settled distance smaller than one settled before it — the sequence must be non-decreasing. Each settle takes the minimum of the remaining tentative labels, and labels only ever decrease toward values at least as large as the current minimum, so settled values come out in non-decreasing order. A dip in that sequence means either the priority queue is misordered or an edge was negative. Prism asserts the ordering as a unit test, which is why the invariant is machine-checked here rather than merely recited.

Question 8

A candidate marks a node settled the moment it is pushed onto the heap. What is the counterexample?

Accepted Answer

A node pushed at a high tentative value can be improved later, so pushing is not proof of finality. Settling means "no cheaper route can exist", and that is only established when a node surfaces as the global minimum. In the default run, I enters the heap at 18 and is improved to 16 before it ever settles; a push-time settle would have frozen 18 and corrupted everything relaxed from I afterwards. Done means popped with the smallest label, never merely seen.

Question 9

You delete the `if (settled.has(node)) continue;` line from a lazy-deletion Dijkstra. What breaks?

Accepted Answer

A node is expanded again from a stale, larger distance, and that stale value leaks into its neighbours. Lazy deletion deliberately leaves old entries in the heap, so a node can surface several times carrying the distances it used to have. Without the guard, the stale entry re-runs the whole relaxation loop with a larger `d`, and any neighbour whose label was still unset takes the worse value. The check is two lines and non-optional — it is the price of not implementing decrease-key.

Question 10

The trace tests a route to F through G: 10 + 5 = 15 against F’s existing label of 13. What happens?

Accepted Answer

Nothing changes — 15 does not beat 13, so no label is written and no heap entry is pushed. Relaxation is one comparison — is the route through this node cheaper than the label already there? Most of the time it is not, and the failure is the normal case rather than an anomaly, because a node is usually reached first by its genuinely cheapest route. Only a strict improvement writes a label and pushes a fresh heap entry, which is why the heap grows more slowly than the edge count.

Question 11

The unsettled labels read D:6, C:10 and G:10. Which node settles next, and on what basis?

Accepted Answer

D — the heap returns the smallest tentative distance, and nothing else enters the comparison. Dijkstra is greedy on exactly one quantity: the smallest tentative distance among unsettled nodes. D wins at 6 despite C and G having been reached over the same edges from B, and no property of the nodes themselves is consulted. That single rule is what the safety proof depends on, which is why the order is not a free choice.

Question 12

The graph has a component the source cannot reach. What are those nodes’ final distances?

Accepted Answer

They stay at infinity, never entering the heap, because no relaxation ever reaches them. A node reaches the heap only by being on the far end of a relaxed edge, so an unreachable node is never pushed and never settled. The loop ends when the heap empties, with fewer settles than nodes, and Prism’s summary line reports exactly that count. Reading a remaining infinity as "no path exists" is the correct interpretation, and it is why the distance array must be initialised to infinity rather than to zero or −1.

Question 13

Weights of zero are allowed. Does a zero-weight edge threaten the correctness argument?

Accepted Answer

No — the proof only needs weights to be non-negative, so equal labels settle in either order safely. The contradiction argument needs "the rest of the path adds at least zero", which a zero edge satisfies exactly. Both endpoints of a zero edge end up with the same distance and settle consecutively in some order, and either order is correct. This is precisely the loophole 0-1 BFS exploits: with only weights zero and one, a deque holds the frontier in order and the heap becomes unnecessary.

Question 14

What does Dijkstra do that BFS cannot, in one sentence an interviewer would accept?

Accepted Answer

It orders the frontier by accumulated cost rather than by hop count, so unequal weights are handled. BFS and Dijkstra are the same algorithm with different queue disciplines: FIFO orders by hop count, a min-heap orders by cost. When every weight is equal those two orderings coincide, which is why BFS is the right tool on unweighted graphs and the heap is pure overhead there. The extra machinery buys exactly one thing — correctness when edges cost different amounts.

Question 15

A* is described as "Dijkstra with a hint". What is the hint, and what must be true of it?

Accepted Answer

An estimate of the remaining distance added to the priority, which must never overestimate. A* pops the node minimising `dist + heuristic(node)` instead of `dist`, which steers the frontier toward the goal rather than expanding evenly in all directions. The heuristic must be admissible — never larger than the true remaining distance — or the greedy proof breaks in exactly the way a negative edge breaks it, and a node can settle too early. Set the heuristic to zero everywhere and you have Dijkstra back, which is why the code diff is about ten lines.

Question 16

You need the actual route, not just its cost. What is the cheapest way to get it?

Accepted Answer

Record a predecessor at each successful relaxation, then walk it backwards from the target. A successful relaxation is exactly the moment the best-known route into a node changes, so writing `prev[to] = node` right there keeps the tree of best routes current for free. Reconstruction is then a backwards walk from the target, reversed — O(path length) and no extra passes. Recomputing routes afterwards is the expensive habit, and interviewers notice it because the fix costs one line inside a branch you already wrote.

Question 17

Prism pushes a duplicate rather than performing decrease-key. What does that trade away, and why is it usually right?

Accepted Answer

A fatter heap for far simpler code — the asymptotics are unchanged because entries are bounded by E. Decrease-key requires a handle into the heap for every node and a sift-up from an arbitrary position, which most standard libraries simply do not expose — Java’s `PriorityQueue` and Python’s `heapq` both lack it. Pushing a duplicate and discarding stale pops costs at most E entries instead of V, keeping the same O((V + E) log V) since log E is within a constant factor of log V on a simple graph. You pay memory and a slightly noisier heap to delete a whole class of pointer bugs.

Question 18

Explain Dijkstra to someone who has never programmed. Say it out loud before revealing.

Accepted Answer

Picture water spreading through a network of pipes from one source, all flowing at the same speed. A junction seven metres of pipe away gets wet at the seven-metre mark, no matter how many routes lead to it — and once it is wet, no later trickle can make it wetter sooner. The algorithm is that, done in steps: every junction keeps a note of the cheapest route found to it so far, and at each turn you look at all the unfinished junctions, pick the one with the smallest note, and declare its number final. You are allowed to do that because any better route would have to leave through some other unfinished junction whose note is already bigger, and then travel further still. That last step is where the picture breaks: it assumes travelling further can never make things cheaper. Give one stretch of pipe a negative length and you have water arriving before it left — routes get cheaper as they go, "the first arrival is final" is simply false, and the method confidently returns the wrong answers with no complaint at all.. The test is whether the listener understands why the greedy step is *allowed*, not merely what it is. A strong answer conveys "the cheapest unfinished place is already finished" as an intuition, and names the assumption that fails — nothing can cost less than nothing.

Dijkstra's algorithm — every question, written out