Dijkstra's Shortest Path Algorithm
Dijkstra's algorithm repeatedly commits to the closest node it has not yet settled, then relaxes its outgoing edges. The commitment is permanent, and the fact that this is safe rests entirely on one assumption — no negative weights — which is worth understanding rather than memorising.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int main() {
int n = 5;
const int INF = 1000000;
vector<vector<int> > w(n, vector<int>(n, INF));
w[0][1] = 4; w[0][2] = 1; w[2][1] = 2;
w[1][3] = 5; w[2][3] = 8; w[3][4] = 3;
vector<int> dist(n, INF);
vector<int> done(n, 0);
dist[0] = 0;
for (int iter = 0; iter < n; iter++) {
int u = -1;
for (int i = 0; i < n; i++) {
if (!done[i] && (u == -1 || dist[i] < dist[u])) u = i;
}
if (dist[u] == INF) break;
done[u] = 1;
for (int v = 0; v < n; v++) {
if (w[u][v] != INF && dist[u] + w[u][v] < dist[v]) {
dist[v] = dist[u] + w[u][v];
}
}
}
for (int i = 0; i < n; i++) cout << dist[i] << ' ';
return 0;
}The O(V squared) adjacency-matrix version — slower than a heap on sparse graphs, but every step is explicit and the shortest route to node 1 is via node 2, not the direct edge.
How it works, step by step
dist holds best-known, not final
Until a node is settled, dist[v] is the shortest distance using only settled nodes as intermediates. It can improve many times. The moment a node is chosen as the minimum, that tentative value becomes final.
Pick the closest unsettled node
The inner selection loop finds the unsettled node with the smallest tentative distance. This is the greedy choice, and the whole algorithm is that choice repeated V times.
Why the greedy choice is safe
Any other route to u would have to leave the settled set through some unsettled node x, and dist[x] >= dist[u] by choice of u. With non-negative weights, the rest of that path can only add more, so no shorter route exists. Negative edges break this argument outright.
Relaxation propagates improvements
For each neighbour v, if reaching v through u is cheaper than the current best, record it. This is the only place dist ever changes, and it is why a node's distance can drop several times before it settles.
Unreachable nodes stay at INF
If the minimum unsettled distance is still INF, no remaining node is reachable and the loop can stop. Without that break, INF + weight overflows and produces nonsense distances that look like real answers.
Complexity
The dominant cost is finding the minimum unsettled node V times; a priority queue replaces that linear scan with a log-time extraction, which is a large win on sparse graphs and no win at all on dense ones where E approaches V squared.
Common bugs
Negative edge weights give wrong answers silently
Dijkstra settles a node permanently, so a negative edge discovered later can offer a cheaper route that is never applied. There is no crash and no warning — just a distance that is quietly too large. Use Bellman-Ford when negative weights are possible.
INF plus a weight overflowing
If INF is INT_MAX and you compute dist[u] + w[u][v] for an unreachable u, the addition wraps to a large negative number that beats every real distance. Either break out when the minimum is INF, as here, or use an INF small enough that INF + maxWeight still fits.
Relaxing edges out of an already-settled node
With a lazy priority queue, the same node can be extracted more than once with stale distances. Without a check that skips entries where the popped distance exceeds dist[u], you redo work and, on some formulations, corrupt results. Watching a node get processed twice is the tell.
Confusing not-yet-settled with unreachable
A node with a finite dist that is not yet in the settled set still has a tentative value that may improve. Reading dist[v] as a final answer before the algorithm finishes gives an overestimate. Only distances of settled nodes are final at any given moment.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why doesn't Dijkstra's algorithm work with negative weights?
Because it permanently settles a node the moment it becomes the closest unsettled one, assuming no later path can be shorter. That assumption relies on every additional edge making a path longer. A negative edge can make a longer route cheaper, and since the node is already settled, the improvement is never applied. Use Bellman-Ford instead.
What is relaxation in Dijkstra's algorithm?
Checking whether going to a neighbour v through the current node u is cheaper than v's best known distance, and updating it if so. The test is dist[u] + weight(u,v) < dist[v]. It is the only operation that ever changes a distance, and a node may be relaxed many times before it is settled.
What is the time complexity of Dijkstra's algorithm?
O(V squared) with a simple array scan to find the minimum, or O((V + E) log V) with a binary heap. The heap version is much faster on sparse graphs where E is close to V, while the array version is competitive on dense graphs where the linear scan is no worse than maintaining the heap.
What is the difference between Dijkstra and BFS?
BFS minimises the number of edges and works only when every edge counts equally; Dijkstra minimises total weight and handles any non-negative weights. BFS uses a plain FIFO queue, while Dijkstra needs a priority queue to always pick the closest frontier node. On a graph where all weights are 1, Dijkstra reduces to BFS.