Sign in to watch this lesson
Algorithms - Graphs II · 4:42
Dijkstra on Sparse Graphs
On a sparse graph the O(n^2) scan for the closest vertex wastes almost all its work, so we hand that job to a container. We run Dijkstra with a std::set (erase the old pair, insert the new one) and with a lazy std::priority_queue that pushes duplicates and skips stale entries, then measure both and show what forgetting the one-line stale check costs.
You will learn
- Implement Dijkstra with std::set<pair<long long,int>>, erasing the old pair before inserting an improved one
- Implement Dijkstra with std::priority_queue and lazy deletion, and explain why the stale-entry check is needed
- Bound both versions by O(m log n) and explain why skipping the check can cost O(n m)
- Avoid the standard traps: max-heap by default, int distances, pushing before assigning d[to]