Dijkstra's algorithm
An algorithm that finds the cheapest paths from one vertex to all others in a graph whose edge weights are never negative, using a min-heap.
In more detail
It repeatedly takes the unfinished vertex with the smallest known distance from the heap, declares that distance final, and relaxes its outgoing edges. This greedy step is correct only because non-negative weights mean no later path can be cheaper. With a heap and lazy deletion it runs in O(E log E) time and O(V + E) space.
Related terms
- min-heap — A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
- relaxation — Checking whether going through vertex u gives a cheaper route to its neighbour v than the best one known, and updating v's distance if so.
- lazy deletion — Leaving outdated entries in a heap instead of removing them, and simply skipping them when they are popped.
- greedy algorithm — An algorithm that builds a solution step by step, always taking the choice that looks best right now and never revisiting it.
- Bellman-Ford algorithm — A shortest-path algorithm that works even with negative edge weights by relaxing every edge V minus one times.
- negative edge weight — An edge whose weight is below zero, as when taking a route earns a refund or credit rather than costing something.
Taught in
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers