Mathematics
The Shortest Path Problem and Dijkstra's Algorithm
Quick fact
Dijkstra's algorithm, developed by Edsger Dijkstra in 1956, can find the shortest path between two points in a graph with non-negative edge weights, and it does so in near-linear time when implemented with a priority queue—the same approach used in modern GPS navigation.
Why this is interesting
When you ask your map app for the quickest route, it finds the path in milliseconds. How does it know?
Read the full explanation
Understanding The Shortest Path Problem and Dijkstra's Algorithm
Imagine you are in a maze where each corridor has a length. You want the shortest route to the exit, but you only know the corridors and their lengths, not the way. Dijkstra's algorithm is like having a checklist of all rooms. You start at the entrance, marking its distance as 0. Then you look at all neighboring rooms, writing down the distance to each. You move to the room with the smallest total distance, and from there you explore its neighbors, updating your notes if you find a shorter way. You keep repeating this—always moving to the unvisited room with the smallest known distance—until you reach the exit. It works because you always expand to the closest possible next step, ensuring that each time you visit a room, you already have the shortest distance to it.
A deeper explanation
Dijkstra's algorithm solves the single-source shortest path problem on a graph with non-negative edge weights. The core idea is to maintain a set of vertices whose shortest distance from the source is known, and a set of tentative distances for the rest. Initially, the source has distance 0, and all others have infinity. In each step, we extract the unvisited vertex with the smallest tentative distance—this vertex is now 'settled' because any other path to it would have to go through an already settled vertex with a larger or equal distance, given non-negative weights. We then 'relax' each edge from this vertex, checking if going through it gives a shorter path to its neighbor. This process repeats until all vertices are settled. The use of a priority queue (often a binary heap) makes the extraction operation efficient, leading to a time complexity of O((V+E) log V) for V vertices and E edges. This greedy strategy succeeds because the problem exhibits an optimal substructure: any shortest path contains shorter paths to its intermediate nodes. However, it fails with negative edge weights, as a negative edge could make a longer path seem better after a vertex is already settled. This algorithm is fundamental in network routing, GPS navigation, and many other optimization tasks.