CSCI2100 · Theorem · Chapter 14 · Graph algorithms
Settling the least tentative vertex is safe
4 steps of prerequisites below it
With nonnegative edge weights, if every settled vertex has its true distance, then an unsettled vertex of least finite tentative label also has its true distance, so Dijkstra finalizes every reachable vertex correctly.
Taught in
- 14.2 Weighted graph frontiers: Dijkstra and Prim · introduced
Uses
- Relaxation · used in its proof, proof step 14.2
- Dijkstra's algorithm · used in its definition, passage 14.2
Used by
No later knowledge point in these notes uses it.
Counterexamples
Everything this builds on, earliest first · 5 steps
Each step comes after its own prerequisites, so reading in this order never needs something you have not met. It is a reading order for these notes, not a diagnosis of what you know.
- Relaxation · 14.2
- Min-priority queue · 3.1
- Binary min-heap · 3.1
- Lazy heap · 14.2
- Dijkstra's algorithm · 14.2
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Each step is used by the one above it, across courses where the notes link them. It ends at a point the notes define without another point.