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

Taught in

References