Dijkstra’s algorithm
Settle the smallest tentative distance in a nonnegative-weight graph, relax outgoing edges, and understand priority-queue and negative-edge boundaries.
· Last updated: 2026-11-07 · 7 min read
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 1983 recollection, Dijkstra explained that he designed the shortest-path algorithm in 1956 to demonstrate the ARMAC computer at the Mathematical Centre in Amsterdam using a 64-city map of the Dutch railway network, working out the method in about twenty minutes over morning coffee without pencil and paper.2 While the original 1959 formulation scanned unsettled vertices in time, Donald B. Johnson introduced -ary heaps in 1977 and Michael L. Fredman and Robert E. Tarjan introduced Fibonacci heaps in 1984, lowering the asymptotic bound to .3
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
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(','));Output:
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.
C++ example
In C++, pairing std::priority_queue with std::greater<> builds a min-heap; lazy insertion together with the if (d > distance[from]) continue; guard implements the priority-queue form directly.
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
struct Edge {
int to;
std::int64_t weight;
};
constexpr std::int64_t kInf = std::numeric_limits<std::int64_t>::max();
std::vector<std::int64_t> dijkstra(
const std::vector<std::vector<Edge>>& graph, int start) {
std::vector<std::int64_t> distance(graph.size(), kInf);
using Entry = std::pair<std::int64_t, int>;
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> pq;
distance[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, from] = pq.top();
pq.pop();
// Discard stale priority-queue entries left over from earlier relaxations.
if (d > distance[from]) continue;
for (const Edge& edge : graph[from]) {
std::int64_t candidate = d + edge.weight;
if (candidate < distance[edge.to]) {
distance[edge.to] = candidate;
pq.push({candidate, edge.to});
}
}
}
return distance;
}
int main() {
// Vertices are S(0), A(1), B(2), T(3), and U(4); no edge reaches U.
const std::vector<std::vector<Edge>> graph{
{{1, 4}, {2, 1}}, {{3, 1}}, {{1, 2}, {3, 5}}, {}, {}};
const auto dist = dijkstra(graph, 0);
for (std::size_t i = 0; i < dist.size(); ++i) {
if (i > 0) std::cout << ',';
if (dist[i] == kInf) std::cout << "INF";
else std::cout << dist[i];
}
std::cout << '\n';
return 0;
}Output:
0,3,1,4,INFCost 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 a binary heap (priority queue) 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;. 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. ↩
- 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. ↩