Question 1

Why does replacing Module F-7's plain queue with Module A-1's min-heap turn BFS's hop-count shortest path into Dijkstra's weighted shortest path?

Accepted Answer

A plain FIFO queue always processes nodes in the order they were discovered, which only corresponds to "closest first" when every edge costs the same; a min-heap instead always extracts whichever discovered node currently has the smallest known accumulated distance, which correctly reflects "closest first" even when edges have different weights. — A FIFO queue's processing order is purely "discovered first, processed first," which only lines up with "closest first" when hop count and distance are the same thing — true only on unweighted graphs. A min-heap instead always surfaces whichever discovered node has the smallest accumulated distance regardless of discovery order, which is exactly what's needed once edges carry different costs — a node discovered later via a cheaper path should be processed before one discovered earlier via a more expensive path, and only a min-heap (not a FIFO queue) guarantees that. Option A dismisses the actual mechanism — the module frames the heap swap as the specific structural change that makes weighted correctness possible, not merely a speed improvement. Option C misattributes the correctness entirely to the `visited` set, which the module presents as a supporting piece (avoiding reprocessing), not the source of the shortest-path guarantee itself. Option D is factually incorrect — a FIFO queue and a min-heap have fundamentally different extraction orders (insertion order vs. smallest-value order), which is precisely the point of the comparison.

Question 2

Why does a negative edge weight break Dijkstra's correctness guarantee, using the module's example (A→B weight 5, A→C weight 2, C→B weight −10)?

Accepted Answer

Dijkstra finalizes B's distance as 5 (processing it before C, since 5 could be extracted before the path through C is fully explored) and never revisits it once marked `visited` — but the true shortest path to B, through C's negative edge (2 + (−10) = −8), is actually much cheaper, and Dijkstra's greedy "never reconsider a finalized node" strategy has no mechanism to discover this after the fact. — The module's example demonstrates precisely this failure: Dijkstra's greedy strategy commits to and finalizes B's distance once it's extracted from the heap, assuming (correctly, under non-negative weights) that nothing cheaper could arrive later. With C's negative edge to B in play, however, a cheaper total route to B exists (through C) that Dijkstra never accounts for, because it has already marked B as `visited` and permanently stopped reconsidering it by the time that cheaper route would have been found. This is exactly the correctness gap the module identifies as requiring Bellman-Ford (Module A-7) instead. Option A fabricates a nonexistent runtime error; the algorithm runs to completion, it just produces an incorrect (too large) distance value. Option C is factually false and irrelevant to the module's point — negative weights are a real, valid modeling choice in many contexts (e.g., representing gains rather than costs), regardless of the module's stance on their plausibility. Option D misunderstands the issue — the actual computed distance value itself is wrong, not merely how it's displayed.

Question 3

According to the module, why is Dijkstra's "always expand the cheapest known frontier node" strategy described as a greedy algorithm with the same character as the ones covered in Module P-15?

Accepted Answer

Dijkstra makes an irreversible, locally-best choice at each step (processing the currently cheapest known node and never revisiting that decision), and this choice is only provably safe under a specific condition (non-negative edge weights) — precisely the same "greedy is correct only when a specific property holds" pattern the module attributes to Module P-15's interval scheduling and knapsack examples. — The module explicitly draws this parallel: Dijkstra commits permanently to processing whichever node currently looks cheapest, never reconsidering that choice later — a locally-best, irreversible decision at each step, which is the defining shape of a greedy algorithm. And just as Module P-15 showed greedy strategies are only correct when a specific structural property holds (the greedy-choice property), Dijkstra's version of that requirement is explicitly non-negative edge weights — remove that condition, and the strategy silently produces wrong answers, exactly paralleling Module P-15's 0/1 knapsack counterexample. Option B directly contradicts the module's explicit, deliberate framing of this as "the same 'greedy choice, provably correct only under specific conditions' theme from Module P-15." Option C is factually incorrect — the module never claims Dijkstra is dynamic programming; it explicitly and repeatedly calls it a greedy algorithm. Option D understates the comparison — the module's point is about a shared conceptual correctness-condition pattern, not merely superficial code-structure similarity.

Module A-6 — Shortest Paths I: Dijkstra's Algorithm

Why BFS Breaks on Weighted Graphs

The Algorithm: BFS With a Min-Heap Instead of a Queue

Why This Only Works With Non-Negative Weights

Where This Shows Up in Your Stack

Summary

Test your knowledge with more question sets

Sign in to keep reading

Discussion