Skip to main content

Dijkstra's Algorithm

What This Concept Is​

Dijkstra repeatedly extracts the smallest tentative distance, finalizes that vertex and relaxes outgoing edges. Every edge must be nonnegative for the standard proof. The lab validates this globally, including unreachable edges, so rejection does not depend on the source. Zero weights are allowed.

An indexed priority queue can decrease keys. A simpler lazy queue inserts a new (distance,vertex) entry after each strict improvement and skips a popped entry when its distance differs from the current label. These implementations have different heap-space bounds.

Why It Matters Here​

The proof explains both correctness and a safe stopping rule. A target's first discovery is not final; its first current minimum extraction is final under the nonnegative assumption. Returning a path needs the exact improving edge ID.

Concrete Examples​

Edges 0→1:5,0→2:1,2→1:1,1→3:2 yield distances [0,2,1,4]. After extracting 2, a new entry (2,1) coexists with stale (5,1); skip the latter. Storing both is correct, but claiming at most one heap record per vertex would be false.

Proof sketch: consider a hypothetically cheaper path to the extracted vertex. Its first not-yet-finalized vertex has a finalized predecessor whose outgoing edge was already relaxed. Nonnegative remaining edges imply a tentative label no larger than that cheaper path, contradicting minimum extraction. With signed edges the remaining suffix may lower the cost, breaking this inequality.

Common Confusion / Misconceptions​

For 0→1:2,0→2:5,2→1:-10, finalizing 1 at 2 is wrong: its true distance is -5. A variant that repeatedly reopens vertices on negative edges is no longer the standard Dijkstra algorithm with its proof and bound. Duplicate heap entries must also be priced for multigraphs where E can greatly exceed V².

How To Use It​

Use O(V+E log(E+2)) time and O(V+E) space for the lab's lazy heap including graph construction; strict improvements produce O(E) insertions. Unit-cost integer arithmetic is an explicit model. A parent path should be acyclic, end at the source and sum to the reported distance. Equal optima may choose different parents; do not turn a tie preference into a correctness requirement.

Check Yourself​

  1. Why is first discovery too early to stop?
  2. Which inequality uses nonnegative weights?
  3. Why does a lazy heap need more than O(V) entries?
  4. What does stale-entry skipping prevent?

Mini Drill or Application​

Implement Lab B. Test a zero cycle, parallel edges with different weights, unreachable vertices and the signed counterexample. Instrument edge scans to observe stale-entry handling; keep empirical counts separate from the proof. See P10.

Read This Only If Stuck​

Find Dijkstra relaxation, finalization, and lazy priority queues in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.