Mathematics
Dijkstra's Algorithm for Shortest Paths in Graphs
Quick fact
Dijkstra's algorithm, published in 1959 by Edsger Dijkstra, was conceived in a cafe in Amsterdam in twenty minutes as a way to demonstrate the power of a new computer, and it still forms the backbone of modern GPS navigation.
Why this is interesting
You're on a road trip and your GPS must instantly compute the fastest route. How does it manage to consider millions of possible paths in the blink of an eye?
Read the full explanation
Understanding Dijkstra's Algorithm for Shortest Paths in Graphs
Imagine a graph where roads are edges and intersections are nodes, each road marked with its travel time. Dijkstra's algorithm starts at your source and gradually "grows" a region of nodes for which you know the shortest distance. Initially, only the source is known (distance 0). The algorithm then repeatedly picks the unvisited node with the smallest known distance—that's where the priority queue helps—and "relaxes" its outgoing edges: for each neighbor, it checks whether going through the current node offers a shorter path than previously known. Once all neighbors are considered, the node is marked as visited, meaning its distance is final. This process continues until all nodes are visited. The genius is that by always choosing the smallest provisional distance, you never need to revisit a node, because any other path would have to pass through an already-visited node with a larger distance.
A deeper explanation
The core mechanism is a greedy strategy supported by the non-negative edge weight assumption. At each step, the algorithm selects the unvisited node with the smallest tentative distance. This is safe because any alternative path to this node would have to pass through some other unvisited node, which has a distance at least as large, and edge weights are non-negative, so the total would be no smaller. Thus, the tentative distance is finalized. This invariant—that visited nodes have their optimal distance—guarantees correctness. The time complexity is O((V + E) log V) with a binary heap, which is why it's so efficient. While Dijkstra's algorithm is optimal for non-negative weights, it fails when negative edges exist, and other algorithms like Bellman-Ford are needed. This algorithm is not just theoretical; it's used in network routing (OSPF) and GPS systems, making it a pillar of modern infrastructure.