Dijkstra's Shortest Path

Dijkstra's algorithm finds the shortest path between nodes in a graph with non-negative edge weights. It operates greedily, maintaining a set of visited nodes and updating distance estimates using the relaxation step: d(v) = min(d(v), d(u) + w(u,v)). The time complexity is optimized to O(E + V log V) using a Fibonacci heap priority queue, demonstrating how structured data layout prevents redundant path searches.

Dijkstra grows a frontier outward from the start, always settling the unvisited node that is currently closest. Because every edge weight is non-negative, no later detour can ever beat a shorter route already found — so once a node is settled, its distance is final and never revisited. That is why route planners and internet routing protocols like OSPF rely on it to compute reliable shortest paths.

Edsger Dijkstra conceived the algorithm in 1956 in about twenty minutes, with no pencil or paper, while resting at an Amsterdam café terrace. He was hunting for a demonstration problem for the ARMAC computer and chose the shortest route between two Dutch cities, Rotterdam and Groningen. He published it three years later in a paper barely three pages long — one of computing's most cited results.