CSCI2100 · Theorem · Chapter 14 · Graph algorithms
Cost of lazy Dijkstra
3 steps of prerequisites below it
With adjacency lists and a binary heap, lazy Dijkstra pushes at most 1 + 2E pairs and takes O(V + E log(E + 2)) time and O(V + E) space.
Taught in
- 14.2 Weighted graph frontiers: Dijkstra and Prim · introduced
Uses
- Logarithmic height and cost · used in its proof, proof step 14.2
- Adjacency matrix and adjacency lists · used in its proof, proof step 14.2
- Lazy heap · used in its definition, passage 14.2
Used by
No later knowledge point in these notes uses it.
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.
- Min-priority queue · 3.1
- Binary min-heap · 3.1
- Logarithmic height and cost · 3.1
- Adjacency matrix and adjacency lists · 13.2
- Lazy heap · 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.