Dijkstra's algorithm

Key characteristics

The algorithm is greedy: it repeatedly selects the not-yet-processed node with the smallest tentative distance and relaxes its outgoing edges. Important elements include:

• Vertices and edges: nodes and connections with numerical weights.
• Nonnegative weights: required to guarantee correctness.
• Tentative distances: provisional shortest-path estimates updated during execution.

How it works

At a high level the steps are:

• Initialize the start node distance to zero and all others to infinity.
• Select the unvisited node with smallest distance.
• For each neighbor, compute a candidate distance through the selected node and update if smaller ("relaxation").
• Mark the selected node as visited and repeat until all reachable nodes are processed.

Complexity and variations

Performance depends on the data structure used for selecting the minimum-distance node. Using a binary heap yields roughly O((V + E) log V). A Fibonacci heap reduces this to O(E + V log V) in theory. A dense graph with an adjacency matrix can be implemented in O(V^2). Practical implementations trade memory and overhead against theoretical bounds.

History, uses and limitations

Named after Edsger W. Dijkstra, who published the method in 1959, the algorithm became foundational in computer science. Common applications include shortest-path routing in GPS and internet routing protocols, pathfinding in games, and resource optimization. Its main limitation is that it cannot handle negative edge weights; algorithms such as Bellman–Ford are used when negative weights or negative cycles must be considered.