Motivation
Lesson 2 of 9 in Coddy's Dijkstra's Algorithm - Graph Algorithms course.
Dijkstra grows a set of vertices whose shortest distance is already known. It always finalizes the closest not-yet-finalized vertex, then uses it to improve (relax) the distances to its neighbors.
Why learn Dijkstra?
- Everywhere: GPS routing, network packet routing, and any least-cost pathfinding.
- Greedy that works: a clean example of a greedy choice that provably gives the optimum, as long as weights are non-negative.
- Foundation: its relaxation idea reappears in A* and other shortest-path algorithms.
Important: Dijkstra assumes no negative weights. Negative edges need Bellman-Ford, the next course.
Try it yourself
This lesson doesn't include a code challenge.
Test yourselfThis lesson includes a short quiz. Start the lesson to answer it and track your progress.
