Dijkstra’s algorithm
Overview
Dijkstra’s algorithm computes shortest distances from a single source vertex to all other vertices in a graph with nonnegative edge weights. When minimizing travel time rather than station count, a direct hop with a heavy delay can lose to a multi-stop route with smaller total cost, so the search always expands the smallest accumulated distance first.
History
In his three-page 1959 paper “A Note on Two Problems in Connexion with Graphs,” Edsger W. Dijkstra solved both the minimum spanning tree problem and the shortest path between two vertices; the shortest-path procedure is Problem 2 of that note.1
In a recollection published in 1983, Dijkstra described computing shortest routes through the Dutch railway network for the ARMAC demonstration at the Mathematical Centre in 1956.2 In an interview recorded in 2001 and published in 2010, he recalled a road map with 64 selected towns, the Rotterdam–Groningen route, and working out the method over coffee in about twenty minutes without pencil and paper.3 While the original 1959 formulation scanned unsettled vertices in time, Donald B. Johnson used -ary heaps in 1977 and Michael L. Fredman and Robert E. Tarjan introduced Fibonacci heaps in 1984, lowering the asymptotic bound to .4
Settling tentative distances and edge relaxation
Initialize the source distance to and every other vertex to . At each step, pick the unsettled vertex with the smallest tentative distance and add it to the settled set . Because all edge weights are nonnegative (), no detour through another unsettled vertex can ever produce a shorter path to :
Once is settled, inspect each outgoing edge and replace if is smaller. This update is called edge relaxation. In the diagram below, the direct edge initially sets , which is then relaxed to after is settled at distance and edge (weight ) is examined.
Executable example
C++20
The C++20 version stores integer costs in long long. Vertex indices and the start are valid, every weight is nonnegative, and each computed path sum is strictly below the maximum long long value. That maximum, INF, is reserved for unreachable vertices and is printed as Infinity to match TypeScript.
#include <cstddef>
#include <iostream>
#include <limits>
#include <vector>
using Distance = long long;
struct Edge { std::size_t to; Distance weight; };
using Graph = std::vector<std::vector<Edge>>;
constexpr Distance INF = std::numeric_limits<Distance>::max();
std::vector<Distance> dijkstra(const Graph& graph, std::size_t start) {
const auto n = graph.size();
std::vector<Distance> distance(n, INF);
std::vector<bool> settled(n, false);
distance[start] = 0;
for (std::size_t step = 0; step < n; ++step) {
auto from = n;
for (std::size_t vertex = 0; vertex < n; ++vertex) {
if (!settled[vertex] && (from == n || distance[vertex] < distance[from])) {
from = vertex;
}
}
// Stop when no reachable unsettled vertex remains.
if (from == n || distance[from] == INF) break;
settled[from] = true;
for (const auto& edge : graph[from]) {
if (settled[edge.to]) continue;
const auto candidate = distance[from] + edge.weight;
if (candidate < distance[edge.to]) distance[edge.to] = candidate;
}
}
return distance;
}
int main() {
// The vertex order is S, A, B, T, U.
const Graph graph{{{1, 4}, {2, 1}}, {{3, 1}}, {{1, 2}, {3, 5}}, {}, {}};
const auto distance = dijkstra(graph, 0);
for (std::size_t i = 0; i < distance.size(); ++i) {
if (i != 0) std::cout << ',';
if (distance[i] == INF) std::cout << "Infinity";
else std::cout << distance[i];
}
std::cout << '\n';
return 0;
}0,3,1,4,InfinityTypeScript
To keep candidate selection visible without extra heap machinery, the example below scans the distance array on a small directed graph. Vertex indices and start lie in 0..graph.length-1, weights are nonnegative safe integers, and all path sums stay within Number.MAX_SAFE_INTEGER.
type Edge = Readonly<{ to: number; weight: number }>;
function dijkstra(graph: readonly (readonly Edge[])[], start: number): number[] {
const distance = new Array<number>(graph.length).fill(Infinity);
const settled = new Array<boolean>(graph.length).fill(false);
distance[start] = 0;
for (let step = 0; step < graph.length; step++) {
let from = -1;
for (let vertex = 0; vertex < graph.length; vertex++) {
if (!settled[vertex] && (from === -1 || distance[vertex]! < distance[from]!)) {
from = vertex;
}
}
// Stop once every remaining unsettled vertex is unreachable (Infinity).
if (from === -1 || distance[from] === Infinity) break;
settled[from] = true;
for (const edge of graph[from]!) {
if (settled[edge.to]) continue;
const candidate = distance[from]! + edge.weight;
if (candidate < distance[edge.to]!) distance[edge.to] = candidate;
}
}
return distance;
}
// Vertices are S(0), A(1), B(2), T(3), and U(4); no edge reaches U.
const graph: Edge[][] = [
[{ to: 1, weight: 4 }, { to: 2, weight: 1 }],
[{ to: 3, weight: 1 }],
[{ to: 1, weight: 2 }, { to: 3, weight: 5 }],
[], [],
];
console.log(dijkstra(graph, 0).join(','));0,3,1,4,InfinityThe output gives the final distances for S, A, B, T, U. Vertex T is reached along at total cost 4, while isolated vertex U remains at Infinity. Breaking as soon as the minimum unsettled distance is Infinity avoids useless iterations over unreachable components.
Cost and practical boundaries
Scanning the array takes time across vertex selections plus across all edge relaxations, totaling time and auxiliary space. This array scan is competitive on dense graphs (), whereas sparse graphs use an indexed binary heap with one entry per vertex and decrease-key updates to run in time.
Two pitfalls arise frequently in production implementations. First, most standard-library priority queues omit an in-place decrease-key operation; instead, implementations push a fresh pair (candidate, v) on every relaxation (lazy insertion) and discard stale entries upon pop with if (d > distance[u]) continue;. With parallel edges allowed, this duplicate-entry version can keep queued entries and takes total time. Omitting that stale-entry guard re-relaxes outgoing edges of the same vertex repeatedly and can blow up running time. Second, if any edge has a negative weight, settling the smallest tentative distance is no longer safe because a later negative edge could undercut an already settled vertex; graphs with negative weights require the Bellman–Ford algorithm.
See also
Footnotes
- E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik 1, 1959, pp.269–271, Problem 2. CWI paper, DOI. ↩
- E. W. Dijkstra, “This Week’s Citation Classic,” Current Contents, 1983-02-14; recollection dated 1982-12-08. Author’s recollection. ↩
- Thomas J. Misa (ed.), “An Interview with Edsger W. Dijkstra,” Communications of the ACM 53(8), 2010, pp.41–47, especially pp.42–43; oral interview recorded in 2001. Paper, DOI. ↩
- Michael L. Fredman, Robert Endre Tarjan, “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms,” 25th Annual Symposium on Foundations of Computer Science (FOCS), 1984, pp.338–346; JACM 34(3), 1987, pp.596–615, DOI. ↩