Dijkstra's Algorithm

Single-Source Shortest Path

1:00

Dijkstra's algorithm finds the shortest path from one source vertex to every other vertex in a non-negative weighted graph using a greedy min-heap strategy.

By the end, you can

Explain the single-source shortest path problem and state Dijkstra's non-negative weight requirement.
Trace Dijkstra's algorithm on a small graph, recording tentative distances, settle order, and the final shortest-path tree.
Apply the relaxation rule to determine whether a distance update occurs for a given edge.
Identify stale heap entries and explain how lazy deletion handles them.
Reconstruct a shortest path by following the prev (parent) map from destination back to source.
Explain why Dijkstra fails on negative edge weights using a concrete counterexample.
State the time complexity of Dijkstra with a binary heap vs. a plain array, and the space complexity.
Describe at least two real-world applications of Dijkstra's algorithm.

Up next in Algorithms & Graph Algorithms