Dijkstra and shortest paths · 2 of 4
Dijkstra
Find the distances from one source when no weight is negative by settling the closest vertex with a min-heap, and adapt the method to another measure of a path, to extra state and to counting shortest paths.
- Dijkstra on sparse graphs Compares a set that deletes old entries with the priority_queue that skips stale ones, the version used in this lesson. cp-algorithms.com (opens in a new tab)
- Lecture 13: Dijkstra’s Algorithm Grows the set of vertices in order of distance, proves it correct and compares an array, a binary heap and a Fibonacci heap as the priority queue, dense graphs against sparse. ocw.mit.edu (opens in a new tab)