Dijkstra's Algorithm Overview and Intuition
What you'll learn: How Dijkstra's algorithm finds the shortest path by greedily selecting the closest unvisited vertex at each step.
The Core Greedy Idea
Dijkstra's algorithm solves the single-source shortest path problem by making a series of greedy choices. At each step, it asks: "Which unvisited vertex can I reach with the smallest total distance from my starting point?" It then locks in that distance as final and explores outward from there.
Think of it like expanding ripples in a pond. You start at the source vertex (where you drop the stone), and the algorithm always processes vertices in order of their distance from the source—closest first, farther later. Once you've determined the shortest distance to a vertex, you never need to revisit it.
Why This Works
The greedy choice property ensures correctness: if you've found the shortest path to vertex A, and you use A to update distances to its neighbors, you're building on guaranteed shortest paths. Because edge weights are non-negative, taking any detour through unvisited vertices can only increase the total distance—so the closest unvisited vertex truly has its final shortest distance.
The Intuition in Action
Imagine finding the fastest route from your home to various destinations in a city. You'd naturally explore nearby locations first, then use those as stepping stones to reach farther places. Dijkstra does exactly this systematically: it maintains a priority queue of vertices ordered by tentative distance, always extracting the minimum to process next.
Key Takeaway: Dijkstra's algorithm is a greedy algorithm that repeatedly selects the closest unvisited vertex, ensuring each vertex's shortest distance is found exactly once, making it efficient for non-negative edge weights.