Dijkstra's algorithm
Algorithm for shortest paths in weighted graphs.
Edsger W. Dijkstra invented his namesake algorithm in 1956 while working as a programmer at the Mathematical Center in Amsterdam. He wanted a problem that non-computing people could grasp, to show off the new ARMAC computer. The idea came to him in about twenty minutes, sitting on a café terrace in Amsterdam with his fiancée, without using pencil or paper. He later implemented it for a simplified map of 64 Dutch cities (chosen so that 6 bits could encode each city number). The algorithm was published three years later, in 1959. A year after inventing it, Dijkstra also rediscovered Prim's minimal spanning tree algorithm while solving a hardware wiring problem.
The algorithm finds the shortest path from a starting node to every other node in a weighted graph—for instance, a road network where nodes are cities and edge costs are distances. It can stop early if only a specific destination is needed. The procedure begins by assigning every node a tentative distance: zero for the start, infinity for all others. It then repeatedly picks the unvisited node with the smallest finite distance, explores its neighbors, and updates their distances if a shorter route is found. This continues until all reachable nodes are visited. A min-priority queue is used to efficiently select the next node.
Originally, Dijkstra's algorithm ran in Θ(|V|²) time, where |V| is the number of nodes. In 1984, Fredman and Tarjan improved this to Θ(|E| + |V| log |V|) using a Fibonacci heap, where |E| is the number of edges. This remains the fastest known single-source shortest-path algorithm for arbitrary directed graphs with non-negative weights, though specialized cases (like integer weights or directed acyclic graphs) can be faster. With preprocessing, techniques like contraction hierarchies can be up to ten million times quicker.
The algorithm works on graphs with positive integer or real edge weights, and can be generalized to any graph where edge weights are partially ordered and labels increase monotonically. It is a core component of network routing protocols such as IS-IS and OSPF, and appears as a subroutine in algorithms like Johnson's. In artificial intelligence, it is known as uniform cost search, a form of best-first search. Dijkstra later remarked that the algorithm's simplicity—forced by designing without paper—became one of the cornerstones of his fame.
- field
- Computer science
- known_for
- Dijkstra's algorithm for shortest paths
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.
Frequently Asked Questions
What are Dijkstra's algorithm's powers and role?
Its core ability is to explore a weighted graph step by step, always expanding the closest unvisited node next, until every reachable node has its minimum distance locked in. This makes it a foundational tool for network routing and pathfinding in computer science.
How does Dijkstra's algorithm's story end?
The process concludes once every node in the graph has been permanently assigned its shortest-path distance from the source. At that point the algorithm halts, having produced a complete distance table for the entire network.
Why is Dijkstra's algorithm important?
It became a cornerstone of graph theory because it offers a reliable, efficient way to solve single-source shortest-path problems in graphs with non-negative edge weights. Its logic underpins many real-world systems, from GPS navigation to internet packet routing.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record