Dijkstra’s algorithm

Also known as: Dijkstra algorithm

On this page 7

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.

  1. Extract the unsettled node u with the minimum tentative distance from the priority queue.
  2. Mark u as settled; its distance is now final and will never change.
  3. For each outgoing edge (u, v) with weight w, test whether dist[u] + w < dist[v].
  4. If the test succeeds, update dist[v], record u as the predecessor of v and insert or decrease v in the queue.
  5. 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.

StructureContentPurpose
Distance arrayBest known cost per nodeHolds tentative and final distances
Predecessor arrayPrevious node on best pathReconstructs the actual route
Priority queueNodes keyed by distanceSelects the next node to settle
Settled setNodes with final distancesPrevents reprocessing stale entries
Core state maintained during execution

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 typeOverall timeBest suited for
Unsorted arrayO(V^2)Dense graphs with E close to V^2
Binary heapO((V + E) log V)Sparse graphs, general use
Fibonacci heapO(E + V log V)Theoretical bound, rarely faster in practice
Bucket queue (Dial)O(E + V C)Small integer weights up to C
Priority queue options and resulting complexity

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.

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.

AlgorithmEdge weightsTime complexityTypical role
Breadth-first searchUnweighted or equalO(V + E)Fewest hops
Dijkstra’s algorithmNon-negativeO((V + E) log V)General single-source routing
A* search algorithmNon-negativeDepends on heuristicSingle target with a good estimate
Bellman-FordNegative allowedO(V E)Negative weights, cycle detection
Floyd-WarshallNegative allowedO(V^3)All pairs on small dense graphs
Dijkstra’s algorithm compared with neighboring algorithms

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.

SituationRecommended approachReason
One source, one targetStop when the target is settledAvoids exploring the whole graph
One source, one target, geometry knownUse A* with a distance heuristicExplores far fewer nodes
Large road network, many queriesAdd contraction hierarchiesQueries become milliseconds
Negative edge weights presentUse Bellman-Ford or JohnsonGreedy settling becomes incorrect
Two endpoints knownRun bidirectional searchRoughly halves the search radius
Deciding how to apply the algorithm

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.