Dijkstra’s algorithm is an algorithm for solving the single-source shortest-path problem in a graph whose edges have nonnegative weights. Starting from a designated source vertex, it determines the minimum total weight needed to reach every reachable vertex, or stops earlier when a particular destination has been reached with a provably optimal distance. Its defining operation is to select the unsettled vertex with the smallest tentative distance and make that distance permanent.
Developed by Edsger W. Dijkstra and published in 1959, the algorithm became a foundational method in computer science, network optimization, and route planning. It combines a simple correctness argument with implementations that can exploit different graph structures and weight domains. Its practical behavior depends strongly on the representation of the graph and the mechanism used to select the next vertex.
The algorithm applies to distances, travel times, communication costs, and other additive quantities, provided that extending a path cannot decrease its accumulated cost. This condition explains both its broad usefulness and its principal limitation: the standard method is not correct for arbitrary negative edge weights.
Historical origin and mathematical setting
Edsger W. Dijkstra devised the algorithm in 1956 while working at the Mathematical Centre in Amsterdam. His paper “A Note on Two Problems in Connexion with Graphs” appeared in Numerische Mathematik, volume 1, in 1959, on pages 269–271. The paper treated both a shortest-path problem and a minimum-total-length connection problem. Its compact presentation helped establish an enduring style of algorithm design: maintain a clearly defined set of partial results and extend it using a locally justified choice.
The mathematical setting comes from graph theory. A graph is written , with vertices , edges , and a weight function . In a directed graph, an edge permits movement from to , but not necessarily in the reverse direction. An undirected edge permits both directions and can be represented computationally by two directed adjacency entries. Weights need not be geometric distances: they can represent tolls, latency, energy consumption, or any suitable additive cost.
For a source vertex , the desired distance to a vertex is
If no path exists, the distance is defined as . The empty path gives . Because all weights are nonnegative, removing a cycle from a walk cannot increase its cost. Thus, whenever a reachable destination has a minimum-cost walk, there is also a simple shortest path to it. Zero-weight cycles may create additional optimal walks without changing the minimum distance.
The usual output is an array of distances and, optionally, predecessor information sufficient to reconstruct one shortest path to each reachable vertex. These are distinct outputs: knowing that a destination is 17 units away does not by itself identify the edges of a route. Multiple optimal routes may exist, so a shortest-path tree need not be unique even when every distance is uniquely determined.
The method belongs to the family of greedy algorithms, because each iteration makes an irrevocable local choice. That choice is not the cheapest edge in the entire graph, nor the cheapest edge leaving the most recently visited vertex. It is the vertex with the smallest total tentative distance from the source. This distinction separates Dijkstra’s algorithm from several superficially similar procedures and is central to its proof of correctness.
Tentative distances, relaxation, and execution
The algorithm maintains a tentative distance for each vertex. Initially, and every other distance is . A predecessor field is initially undefined. A vertex is called settled when the algorithm has established that its tentative distance equals its actual shortest-path distance. Discovered but unsettled vertices form the active frontier.
The fundamental update is relaxation. When an edge is examined, the algorithm compares the current estimate with the cost of reaching through . If
it assigns and records . A relaxation therefore replaces an existing route by a strictly cheaper one. It does not mean that the new estimate is already final.
A priority queue organizes the frontier by tentative distance. The following pseudocode uses an indexed queue, in which each queued vertex has one entry and its priority can be decreased:
for each vertex v:
d[v] = infinity
predecessor[v] = undefined
settled[v] = false
d[source] = 0
Q.insert(source, 0)
while Q is not empty:
u = Q.extract_min()
settled[u] = true
for each edge (u, v) with weight w:
if settled[v]:
continue
candidate = d[u] + w
if candidate < d[v]:
d[v] = candidate
predecessor[v] = u
if Q contains v:
Q.decrease_key(v, candidate)
else:
Q.insert(v, candidate)
Only discovered vertices enter this queue. An alternative initializes the queue with every vertex, including those with infinite distance; that version can stop when its minimum key is infinite. The two versions compute the same finite distances, but their memory use and work on disconnected graphs can differ.
For a single destination , execution may stop as soon as is extracted with its current minimum key and settled. Stopping when is first discovered is incorrect: the first route reaching it may later be improved. For a distance-limited search, execution can stop when the smallest unsettled distance exceeds the permitted radius. Nonnegative weights guarantee that no subsequent vertex will fall inside that radius.
Once a destination has been settled, its path can be reconstructed by following predecessor pointers backward to the source and reversing the sequence. This takes time proportional to the number of edges in the returned path. Distances to vertices that remain unsettled after an early stop are only tentative; an interface that returns such partial results must distinguish them from finalized answers.
Why the greedy choice is correct
The correctness argument rests on two facts. First, every finite tentative distance is the length of an actual path from the source. Consequently, it is an upper bound on the optimum:
Second, once a vertex is settled, its value is exact. This second property is the central loop invariant: at the beginning of each iteration, every already settled vertex satisfies .
Suppose the invariant holds, and let be the unsettled vertex with minimum tentative distance. Consider a shortest path from to . If , let be the first unsettled vertex on that path, and let be its preceding vertex. The vertex is settled. When was processed, its edge to was relaxed. A prefix of a shortest path is itself a shortest path to its endpoint, so that relaxation established .
All edges on the remainder of the path have nonnegative weight. Therefore,
Because has the smallest tentative distance among unsettled vertices,
Together with the upper-bound property , this proves equality. Settling therefore preserves the invariant. Initialization handles the source, and induction establishes correctness for every vertex subsequently settled.
The proof explains why zero-weight edges are permitted. The required inequality is non-strict: a later vertex on a shortest path may have exactly the same distance as an earlier one. Equal-key vertices can be settled in different orders without changing the final distance values. The predecessor tree can nevertheless differ, depending on tie-breaking and adjacency order.
Negative weights invalidate the crucial inequality. For example, take edges of weight 2, of weight 5, and of weight . The algorithm settles at distance 2 before examining , although the route through has cost 1. This graph contains no cycle at all: a negative cycle is not required to make the standard algorithm fail.
A variant that repeatedly reopens settled vertices is no longer governed by this proof or by the usual running-time bound. The relevant requirement is not merely the absence of negative cycles, but the nonnegativity of the edge costs under the distance representation being used. This distinction is important in formal verification, where the input assumptions, arithmetic behavior, queue operations, and invariant must all match the implementation.
Worked example and interpretation of the output
Consider a directed graph with source and vertices . Its edges are with weight 4, with weight 1, with weight 2, with weight 5, with weight 1, with weight 7, and with weight 3. Initially, only the source has a finite tentative distance.
Settling discovers at distance 4 and at distance 1. The next settled vertex is , not , because the choice depends on total distance from the source. Relaxing the outgoing edges of improves to and discovers at . The previously found direct route to is therefore replaced before becomes permanent.
The successive labels are:
| Vertex just settled | |||||
|---|---|---|---|---|---|
| Initial state | 0 | ||||
| 0 | 4 | 1 | |||
| 0 | 3 | 1 | 6 | ||
| 0 | 3 | 1 | 4 | 10 | |
| 0 | 3 | 1 | 4 | 7 | |
| 0 | 3 | 1 | 4 | 7 |
When is settled at distance 3, it improves from 6 to 4 and discovers at 10. Settling then improves to 7. The final shortest route to is . It contains four edges, although the three-edge route costs more. Dijkstra’s algorithm minimizes total weight, not the number of edges.
The predecessor relationships are , , , and . Together they form a tree rooted at , restricted to reachable vertices. The original graph can contain cycles and many additional edges; those edges do not need to appear in this particular representation of optimal routes.
If an edge of weight 3 replaced the weight-5 edge, two shortest routes to would have cost 4: the direct continuation from , and the route through . A strict-improvement implementation would retain whichever predecessor first established that distance. Retaining all equally optimal predecessors requires additional logic.
That distinction becomes especially important with zero-weight cycles. One predecessor per vertex can still describe a shortest-path tree, but the collection of all distance-preserving edges can contain cycles. There may be infinitely many optimal walks that repeatedly traverse such a cycle, although only finitely many simple paths in a finite graph. Computing distances, returning one optimal route, and enumerating every optimal route are therefore different computational tasks.
Data structures and computational complexity
The algorithm’s time complexity depends on how it selects the minimum-distance vertex and stores outgoing edges. Let and . A simple implementation scans all unsettled vertices to find the minimum at each iteration. This costs overall for selection, plus for edge examinations. For a simple graph, the resulting bound is usually written . This version remains useful for dense graphs and modest problem sizes.
An adjacency list stores only existing edges and allows the algorithm to inspect all outgoing edges of a settled vertex in time proportional to its outdegree. Combined with an indexed binary heap, minimum extraction and decrease-key each take time. There are at most extractions and at most successful decreases or insertions, giving
On a connected undirected graph with at least two vertices, , so the bound is often abbreviated to .
A Fibonacci heap provides amortized decrease-key and amortized extract-min, producing the classical bound
Michael Fredman and Robert Tarjan introduced Fibonacci heaps in work published in 1987. Their theoretical advantage does not imply universal practical superiority: pointer-heavy structures, memory allocation, and cache behavior can outweigh the reduction in asymptotic operation counts. Simpler heaps frequently perform well on ordinary workloads.
Many implementations avoid decrease-key entirely. Whenever a better distance is found, they insert a new pair containing that distance and the vertex. Earlier entries remain in the heap and are discarded when extracted if their stored distance no longer matches the current label. This lazy version performs at most one insertion per successful relaxation, plus the source insertion. Its queue can occupy space, and a general bound is . For simple graphs, this is commonly expressed using .
Weight restrictions permit further specialization. If every edge has unit weight, breadth-first search solves the problem in time without a heap. If weights are only 0 or 1, a double-ended queue supports a linear-time method often called 0–1 BFS. For bounded nonnegative integer weights, bucket queues can exploit the restricted key range. A radix heap exploits both integer keys and the fact that extracted minimum distances never decrease.
The graph normally requires storage in adjacency-list form. Distances, predecessors, settled flags, and an indexed queue add auxiliary storage. Actual costs also depend on the data structures used for vertex identifiers and on whether weights fit in fixed-width machine words; the standard bounds assume constant-time arithmetic and comparisons.
Implementation details and numerical reliability
A correct abstract algorithm can still be implemented incorrectly through queue handling, arithmetic, or ambiguous output conventions. In a lazy heap, an extracted entry must be checked before its outgoing edges are processed. A typical test discards an entry when . Alternatively, an implementation can maintain settled flags and skip vertices already finalized. Processing stale entries repeatedly may preserve distances under some implementations, but it can destroy the intended efficiency and complicate early termination.
Fixed-width integer overflow is a particularly serious issue. If a large positive distance plus an edge weight wraps into a negative or small value, the algorithm may interpret an extremely expensive route as the best one. A sentinel for infinity must therefore be distinguished safely from finite distances, and additions must remain within the supported range or use explicit overflow checks. Arbitrary-precision integers avoid overflow but make arithmetic cost depend on the number of bits in each value.
Floating-point weights introduce different limitations. Mathematical addition of nonnegative real numbers is exact in the proof, whereas machine addition usually rounds. Distinct path costs can become indistinguishable, and different addition orders can produce slightly different values. The implementation should have a defined numeric model rather than silently treating floating-point results as exact real arithmetic. NaN values are particularly unsuitable because their comparisons do not define the ordering expected by a heap; infinities also require an explicit interpretation.
Tie-breaking influences reproducibility. If two vertices have the same tentative distance, either can be settled first, but the resulting predecessor tree may depend on heap behavior, input order, or vertex identifiers. A secondary ordering can make selection deterministic. For strict-improvement relaxation, equal-cost alternatives do not replace an existing predecessor. Changing the test from to without considering zero-weight edges and predecessor management can produce unnecessary updates or problematic reconstruction behavior.
The graph must also correspond to the cost model throughout the search. If an edge weight changes after the algorithm has settled relevant vertices, the invariant may no longer hold. Dynamic networks require a consistent snapshot, a new computation, or a specialized update method. Similarly, an undirected edge with unequal costs in the two directions is better modeled as two directed edges, not as one symmetric weight.
Testing can use independently checkable properties rather than only known examples. For a completed run, every reachable edge should satisfy
Each reachable non-source vertex should have a predecessor edge realizing equality, and its predecessor chain should reach the source. These conditions, together with and suitable treatment of unreachable vertices, provide a certificate of shortest-path distances: edge inequalities give lower bounds on all routes, while predecessor paths demonstrate that the reported values are attainable.
Relationship to other shortest-path methods
Dijkstra’s algorithm occupies a specific position among shortest-path techniques rather than replacing them all. Breadth-first search is its unit-weight counterpart: vertices are processed in layers of equal edge count, so a first-in, first-out queue suffices. In artificial-intelligence search terminology, uniform-cost search applies the same least-accumulated-cost principle to a state space that may be generated during exploration rather than stored as a complete graph. On infinite state spaces, completeness requires additional conditions; finite-graph correctness alone does not settle termination.
The Bellman–Ford algorithm permits negative edge weights and can detect a negative cycle reachable from the source. Its conventional worst-case running time is . It repeatedly propagates improvements rather than permanently settling vertices in Dijkstra’s order. A directed acyclic graph admits another alternative: processing vertices in topological order solves single-source shortest paths in , even when some edges are negative, because there are no directed cycles to complicate the dependency order.
A* search adds a destination-oriented heuristic and orders vertices by
where is the best known source-to-vertex cost. Dijkstra’s algorithm is recovered when is identically zero. A consistent heuristic satisfies , which makes the reduced costs nonnegative. This connects A* directly to Dijkstra’s label-setting principle. An admissible but inconsistent heuristic can require reopening vertices in graph-search implementations.
Reweighting also underlies Johnson’s algorithm for all-pairs shortest paths. When a directed graph has no negative cycle, a Bellman–Ford computation supplies vertex potentials that transform its edge weights into nonnegative reduced weights. Dijkstra’s algorithm then runs from each source, and the potentials convert the resulting distances back to the original scale. For dense all-pairs problems, the Floyd–Warshall algorithm instead uses dynamic programming with time and a distance matrix.
Dijkstra’s method also resembles Prim’s algorithm for a minimum spanning tree, but the optimization objectives differ. Prim’s priority measures the cheapest individual edge connecting a vertex to the growing tree. Dijkstra’s priority measures the cheapest complete path from the source. A shortest-path tree need not have minimum total edge weight, and a minimum spanning tree need not preserve source-to-vertex shortest distances.
Bidirectional Dijkstra runs one search forward from the source and another backward from the destination, using reversed edges for the backward search in a directed graph. Correct termination depends on a bound, not merely on the searches first meeting. A standard condition compares the best complete route found so far with the sum of the minimum unsettled forward and backward distances; once that lower bound cannot improve the route, the search can stop.
Routing, navigation, and extended models
A prominent application is link-state routing. In Open Shortest Path First, a router uses link-state information to build a representation of network topology and compute shortest paths rooted at itself. Edge weights represent configured routing costs rather than necessarily physical distance or current delay. The resulting shortest-path structure helps determine next hops. Equal-cost alternatives may support multiple next hops, so routing implementations can need richer output than a single predecessor tree.
This use should be distinguished from Internet-wide interdomain routing. The Border Gateway Protocol exchanges reachability and path information between autonomous systems and applies policy-based route selection; it is not simply Dijkstra’s algorithm operating on the entire Internet. Even within a link-state system, the shortest-path computation is only one component alongside topology distribution, failure detection, protocol state, and forwarding-table installation.
Road navigation provides another major setting. Vertices can represent junctions and edges road segments, with weights based on length or estimated travel time. One-way streets map naturally to directed edges. Turn restrictions reveal a limitation of a naive junction-only model: the legality or cost of leaving an intersection may depend on the incoming road. An expanded state can therefore include the incoming directed road segment, allowing legal turns and turn penalties to become transitions with appropriate costs.
For repeated queries on a large, mostly stable road network, plain Dijkstra search may explore too many vertices. Preprocessing methods such as contraction hierarchies add shortcut edges that preserve shortest-path distances while enabling queries to examine a much smaller search region. Such methods retain connections to Dijkstra-style searches but trade preprocessing time and extra storage for faster queries. The trade-off changes when weights or road availability change frequently.
Multi-source search initializes several source vertices with distance zero. It computes the distance to the nearest source and can assign each reached vertex to a nearest facility. Equivalently, a new super-source can connect to every original source by a zero-weight edge. This supports network-based service-area calculations. On image grids, vertices can represent pixels or voxels, with nonnegative transition costs derived from local appearance or permitted movement; the resulting distances depend on the graph model and are not automatically exact Euclidean distances.
More complex objectives require additional assumptions or different algorithms. In time-dependent routing, a label-setting approach can work under a first-in, first-out condition: departing along an edge later must not allow arrival earlier than departing sooner. Resource-constrained routing, such as minimizing travel time subject to a fuel limit, generally cannot be represented by one scalar distance per physical vertex without expanding the state. Likewise, multiple competing objectives may require sets of nondominated labels. The applicability of Dijkstra’s principle depends on whether the chosen state and cost representation preserve the ordering properties needed to finalize a label safely.