Dijkstra’s algorithm is a single-source shortest path algorithm that computes the minimum total distance from one starting node to every other reachable node in a weighted graph, provided that all edge weights are non-negative. Published by Edsger W. Dijkstra in 1959, it remains one of the most widely taught and deployed algorithms in programming, from network routing protocols to map navigation and game pathfinding.
The algorithm is a classic greedy algorithm: at every step it permanently settles the unvisited node with the smallest tentative distance, and that local choice is provably optimal because no negative edge can later produce a shorter route. With a binary heap as its priority queue, it runs in O((V + E) log V) time, which makes it practical on graphs with millions of edges.
How Dijkstra’s algorithm settles nodes
Dijkstra’s algorithm works by maintaining a tentative distance for every node and repeatedly finalizing the closest one. Initially the source has distance 0 and every other node has distance infinity. The algorithm then loops until the priority queue is empty or the target has been settled.
- Extract the unsettled node
uwith the minimum tentative distance from the priority queue. - Mark
uas settled; its distance is now final and will never change. - For each outgoing edge
(u, v)with weightw, test whetherdist[u] + w < dist[v]. - If the test succeeds, update
dist[v], recorduas the predecessor ofvand insert or decreasevin the queue. - Repeat until no reachable unsettled node remains.
The update in step 4 is called edge relaxation. Storing predecessors builds a shortest path tree rooted at the source, so any individual route can be reconstructed by walking predecessor links backward from the destination. The correctness argument rests on one invariant: when a node is extracted, no shorter path to it can exist, because every alternative path would have to pass through a node whose distance is already at least as large.
The following table summarizes the data structures that a typical implementation keeps in memory.
| Structure | Content | Purpose |
|---|---|---|
| Distance array | Best known cost per node | Holds tentative and final distances |
| Predecessor array | Previous node on best path | Reconstructs the actual route |
| Priority queue | Nodes keyed by distance | Selects the next node to settle |
| Settled set | Nodes with final distances | Prevents reprocessing stale entries |
Time complexity and priority queue choices
The running time of Dijkstra’s algorithm depends almost entirely on the priority queue implementation. The algorithm performs V extract-minimum operations and up to E decrease-key or insert operations, so the cost of those two operations determines the overall bound in Big O notation.
| Queue type | Overall time | Best suited for |
|---|---|---|
| Unsorted array | O(V^2) | Dense graphs with E close to V^2 |
| Binary heap | O((V + E) log V) | Sparse graphs, general use |
| Fibonacci heap | O(E + V log V) | Theoretical bound, rarely faster in practice |
| Bucket queue (Dial) | O(E + V C) | Small integer weights up to C |
Most production code uses a binary heap with lazy deletion: instead of a true decrease-key operation, it pushes a duplicate entry and discards stale entries when they are popped. This approach increases the heap size to O(E) but keeps the code simple and cache-friendly, and it usually outperforms a Fibonacci heap because of much smaller constant factors. The space complexity is O(V + E) for an adjacency list representation.
Comparison with related shortest path methods
Dijkstra’s algorithm occupies a specific niche among graph search methods: it handles weighted graphs with non-negative weights from a single source. Other algorithms in the same family relax one of those conditions or add extra information.
| Algorithm | Edge weights | Time complexity | Typical role |
|---|---|---|---|
| Breadth-first search | Unweighted or equal | O(V + E) | Fewest hops |
| Dijkstra’s algorithm | Non-negative | O((V + E) log V) | General single-source routing |
| A* search algorithm | Non-negative | Depends on heuristic | Single target with a good estimate |
| Bellman-Ford | Negative allowed | O(V E) | Negative weights, cycle detection |
| Floyd-Warshall | Negative allowed | O(V^3) | All pairs on small dense graphs |
Breadth-first search is effectively Dijkstra’s algorithm with a FIFO queue instead of a priority queue, which works only because every edge has the same cost. The A* search algorithm adds a heuristic estimate of the remaining distance to the priority key; with a zero heuristic, A* becomes Dijkstra’s algorithm exactly. Bellman-Ford trades speed for the ability to handle negative edges and is better described as dynamic programming than as a greedy method.
Practical use and implementation choices
Dijkstra’s algorithm is the default choice whenever a program needs exact shortest paths on a graph with non-negative costs such as distance, latency or travel time. The OSPF and IS-IS link-state routing protocols run it on every router to build forwarding tables, and many map applications use it as the baseline before applying faster preprocessing techniques.
| Situation | Recommended approach | Reason |
|---|---|---|
| One source, one target | Stop when the target is settled | Avoids exploring the whole graph |
| One source, one target, geometry known | Use A* with a distance heuristic | Explores far fewer nodes |
| Large road network, many queries | Add contraction hierarchies | Queries become milliseconds |
| Negative edge weights present | Use Bellman-Ford or Johnson | Greedy settling becomes incorrect |
| Two endpoints known | Run bidirectional search | Roughly halves the search radius |
An early exit is the most valuable optimization for point-to-point queries: once the target is extracted from the queue, its distance is final and the loop can stop. Bidirectional Dijkstra runs two searches, one forward from the source and one backward from the target, and stops when their frontiers meet under a correct termination condition.
Limitations and common mistakes
The most serious limitation is that Dijkstra’s algorithm fails with negative edge weights. A negative edge can make a longer-looking path cheaper after a node has already been settled, which breaks the greedy invariant and produces silently wrong results rather than an error.
- Ignoring stale heap entries: with lazy deletion, a popped node that is already settled must be skipped, or work and errors multiply.
- Integer overflow: using the maximum integer as infinity and then adding a weight can wrap around to a negative value.
- Wrong termination: stopping when the target is first discovered, rather than when it is extracted, may return a suboptimal path.
- Adding a constant to fix negative weights: shifting every weight changes which path is shortest, because paths with more edges are penalized more.
- Using an adjacency matrix on sparse graphs: this forces O(V^2) work even when E is close to V.
On very large graphs, plain Dijkstra’s algorithm also explores a roughly circular region around the source, so it visits many irrelevant nodes. That behavior motivates goal-directed variants and preprocessing methods, which keep the same correctness guarantee while cutting query time by orders of magnitude.
A non-technical view
Imagine spilling water at one spot on a map where roads are channels of different lengths. The water reaches the nearest junction first, then the next nearest, and so on. Dijkstra’s algorithm does the same thing in order: it always deals with the closest place it has not finished yet.
Once a place is reached this way, the route to it is guaranteed to be the shortest one, because any other route would have to be longer. The key takeaway is that the method is reliable as long as no road has a negative length, which in real travel never happens.
A concrete example
A logistics company models a regional delivery network as a graph of 4,200 intersections and 11,000 road segments, with each edge weighted by expected travel time in seconds. A dispatcher needs the fastest route from the depot to every customer address scheduled for the day, so the routing service runs Dijkstra’s algorithm once from the depot node with a binary heap.
Because all travel times are positive, a single run produces a complete shortest path tree in well under 50 milliseconds on a standard server. The service then reconstructs each route by following predecessor links from the customer node back to the depot. The outcome is one computation serving 180 deliveries, instead of 180 separate point-to-point searches, and the drivers receive routes that are provably optimal for the current travel time estimates.