Dijkstra's algorithm

Lore & Background

Dijkstra designed the algorithm in about twenty minutes while sitting on a café terrace in Amsterdam with his fiancée. He was thinking about the shortest path problem and created the algorithm without pencil and paper, which he later said forced him to avoid unnecessary complexities. The algorithm was originally implemented for the ARMAC computer to demonstrate its capabilities using a simplified transportation map of 64 cities in the Netherlands. The original algorithm ran in Θ(|V|²) time, where |V| is the number of nodes. Later, Fredman and Tarjan proposed a Fibonacci heap priority queue to optimize the running time to Θ(|E| + |V| log |V|), which is asymptotically the fastest known for arbitrary directed graphs with unbounded non-negative weights. The algorithm is commonly used on graphs with positive integer or real edge weights and can be generalized to partially ordered weights with monotonically non-decreasing labels. It is employed in network routing protocols such as IS-IS and OSPF, and as a subroutine in algorithms like Johnson's algorithm.

Reader's Guide

Dijkstra's algorithm is significant as one of the most fundamental and widely used algorithms in computer science. It provides an efficient method for solving the single-source shortest path problem on weighted graphs with non-negative edges. The algorithm's influence extends across many fields, including artificial intelligence, where it is formulated as uniform cost search and as an instance of best-first search. Its practical applications include network routing protocols (IS-IS and OSPF), GPS navigation systems, and as a building block for more complex algorithms. The algorithm's elegance and efficiency have made it a standard topic in computer science education and a cornerstone of Dijkstra's fame. Its legacy includes ongoing optimizations, such as contraction hierarchies, which can be up to seven orders of magnitude faster when preprocessing is allowed.

Did You Know?

• Dijkstra designed the algorithm in about twenty minutes while sitting on a café terrace in Amsterdam with his fiancée.
• The algorithm was originally implemented for the ARMAC computer using a simplified map of 64 cities in the Netherlands.
• The original algorithm ran in Θ(|V|²) time; later optimization using a Fibonacci heap reduced it to Θ(|E| + |V| log |V|).
• Dijkstra's algorithm is used in network routing protocols such as IS-IS and OSPF.