When I first sat down to understand how computers find the “shortest” way from one point to another — whether that’s a road network, a computer network, or a dependency graph — Dijkstra’s algorithm is the name that comes up almost immediately. I want to walk through it the way I understood it myself: as a systematic, greedy method for finding the shortest path from a single source node to every other node in a graph, as long as none of the edge weights are negative. It matters because so much of modern routing — GPS navigation, network packet routing, even some AI planning systems — rests on this one idea.
History and Background
I learned that this algorithm was conceived by the Dutch computer scientist Edsger W. Dijkstra in 1956, and he published it in 1959. What I find charming about the origin story is that he designed it in about twenty minutes, without pen or paper, while thinking about how to demonstrate the capabilities of a new computer (the ARMAC) to a general audience — he wanted a problem that a layperson could understand and a computer could solve impressively. He picked the shortest route between two cities in the Netherlands. Since then, the algorithm has become one of the most cited and most implemented algorithms in computer science, forming the backbone of routing protocols like OSPF and IS-IS.
Problem Statement
I would state the problem like this: given a weighted, directed or undirected graph $G = (V, E)$ with non-negative edge weights, and a designated source vertex $s$, I want to determine the shortest possible distance from $s$ to every other vertex in $V$, and ideally reconstruct the actual path.
Core Concepts
Before I get into the mechanics, I want to lay out the vocabulary I rely on:
- Vertex (node): a point in the graph.
- Edge: a connection between two vertices, carrying a weight (cost/distance).
- Weighted graph: a graph where every edge has an associated non-negative cost.
- Relaxation: the process of checking whether going through a particular vertex offers a shorter path to another vertex than what I currently know.
- Tentative distance: my current best estimate of the shortest distance from the source to a vertex, which may improve as the algorithm proceeds.
- Visited/settled set: vertices for which I have already found the guaranteed shortest distance.
- Priority queue: the data structure I use to always pick the next closest unvisited vertex efficiently.
How It Works
Here is the sequence I follow when running the algorithm by hand:
- I assign a tentative distance value to every vertex: zero for the source, infinity for all others.
- I mark all vertices as unvisited and put them in a set of “vertices to check.”
- I set the source as the current vertex.
- For the current vertex, I look at all of its unvisited neighbors and calculate their tentative distance through the current vertex. If this new distance is smaller than the previously recorded one, I update it.
- Once I’ve considered all neighbors of the current vertex, I mark it as visited — it is removed from the unvisited set and will never be checked again.
- I pick the unvisited vertex with the smallest tentative distance and make it the new current vertex.
- I repeat steps 4–6 until every vertex has been visited, or the smallest tentative distance among unvisited vertices is infinity (meaning remaining vertices are unreachable).
Working Principle
The internal logic rests on a greedy assumption: once I’ve settled on the shortest distance to a vertex, that distance can never be improved later — because all edge weights are non-negative, any alternative path would have to pass through an unvisited vertex whose current distance is already at least as large. This is exactly why Dijkstra’s algorithm fails on graphs with negative weights: the greedy “lock-in” assumption breaks down if a later, cheaper edge could reduce a distance I already finalized.
Mathematical Foundation
I define $d(v)$ as the tentative distance to vertex $v$, and $w(u,v)$ as the weight of edge $(u,v)$. The relaxation step is expressed as:
$$ d(v) = \min\big(d(v),\ d(u) + w(u,v)\big) $$
The algorithm terminates with the guarantee:
$$ d(v) = \delta(s,v) \quad \text{for every } v \in V $$
where $\delta(s,v)$ is the true shortest-path distance from $s$ to $v$.
Using a binary heap as the priority queue, the overall running time is:
$$ O\big((|V| + |E|) \log |V|\big) $$
Diagrams
flowchart TD
Start([Start]) --> Init[Set dist=0 for source, infinity for others]
Init --> Loop{Any unvisited vertex left?}
Loop -- No --> End([Done])
Loop -- Yes --> Pick[Pick unvisited vertex with min distance]
Pick --> Relax[Relax all its neighbors]
Relax --> Mark[Mark vertex as visited]
Mark --> LoopPseudocode
function Dijkstra(Graph, source):
for each vertex v in Graph:
dist[v] = infinity
prev[v] = undefined
dist[source] = 0
Q = set of all vertices in Graph // priority queue keyed by dist
while Q is not empty:
u = vertex in Q with smallest dist[u]
remove u from Q
for each neighbor v of u still in Q:
alt = dist[u] + weight(u, v)
if alt < dist[v]:
dist[v] = alt
prev[v] = u
return dist[], prev[]
Step-by-Step Example
I’ll use the small graph shown in the diagram above, with source vertex A.
- Initial: dist = {A:0, B:∞, C:∞, D:∞, E:∞}
- Visit A: relax B (A+4=4), relax C (A+1=1). dist = {A:0, B:4, C:1, D:∞, E:∞}
- Visit C (smallest, 1): relax B via C (1+2=3 < 4, update), relax D via C (1+5=6). dist = {B:3, D:6}
- Visit B (smallest, 3): relax D via B (3+1=4 < 6, update). dist = {D:4}
- Visit D (smallest, 4): relax E via D (4+3=7). dist = {E:7}
- Visit E (7): no unvisited neighbors left.
Final shortest distances from A: B=3, C=1, D=4, E=7.
Time Complexity
- Using a simple array to find the minimum: $O(V^2)$, good for dense graphs.
- Using a binary heap priority queue: $O((V+E)\log V)$, better for sparse graphs.
- Using a Fibonacci heap: $O(E + V \log V)$, the best known asymptotic bound.
Best, average, and worst case are effectively the same order because the algorithm always processes every vertex and edge once, regardless of input arrangement.
Space Complexity
I need arrays for distance, previous-vertex tracking, and a visited flag, each of size $O(V)$, plus the priority queue which can hold up to $O(V)$ entries and the adjacency list which takes $O(V+E)$. Overall space is $O(V+E)$.
Correctness Analysis
The correctness proof I find most convincing is by induction on the order in which vertices are settled. The claim is: when a vertex $u$ is removed from the priority queue (settled), $dist[u]$ equals the true shortest distance $\delta(s,u)$. This holds because any path to $u$ that is shorter than $dist[u]$ would have to pass through some unvisited vertex $x$ with $dist[x] \geq dist[u]$ — but since all weights are non-negative, extending that path further can only add more cost, so it can never beat $dist[u]$. This is precisely why the non-negative weight condition is essential to the proof.
Advantages
- Guarantees the optimal shortest path for graphs with non-negative weights.
- Efficient with a good priority queue implementation.
- Naturally produces shortest paths to all reachable vertices from the source, not just one target.
- Well understood, widely implemented, and easy to adapt (e.g., bidirectional search, A*).
Disadvantages
- Fails or gives incorrect results with negative edge weights.
- Less efficient than specialized algorithms for very large or dynamic graphs.
- Doesn’t inherently use any goal-directed heuristic (unlike A*), so it can explore more nodes than necessary when only one destination matters.
Applications
- GPS and mapping software for route planning.
- Network routing protocols (OSPF, IS-IS).
- Robotics motion planning.
- Airline and logistics route optimization.
- Telecommunication network design.
Implementation in C
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#define V 5 // number of vertices
// Find the unvisited vertex with the minimum distance
int minDistance(int dist[], bool visited[]) {
int min = INT_MAX, minIndex = -1;
for (int v = 0; v < V; v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}
void dijkstra(int graph[V][V], int src) {
int dist[V];
bool visited[V];
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, visited);
if (u == -1) break; // remaining vertices unreachable
visited[u] = true;
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] &&
dist[u] != INT_MAX &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t %d\n", i, dist[i]);
}
int main() {
// 0=A, 1=B, 2=C, 3=D, 4=E
int graph[V][V] = {
{0, 4, 1, 0, 0},
{4, 0, 2, 1, 0},
{1, 2, 0, 5, 0},
{0, 1, 5, 0, 3},
{0, 0, 0, 3, 0}
};
dijkstra(graph, 0);
return 0;
}
Sample Input and Output
Input: the adjacency matrix in the code above, source vertex A (index 0).
Output:
Vertex Distance from Source
0 0
1 3
2 1
3 4
4 7
This matches the manual walkthrough I did earlier.
Optimization Techniques
- Replace the linear-scan minimum search with a binary min-heap to cut running time on sparse graphs.
- Use a Fibonacci heap when decrease-key operations dominate, for the best theoretical bound.
- Apply early termination once the target vertex is settled, if I only need a single destination.
- Use bidirectional Dijkstra (searching simultaneously from source and target) to cut the search space roughly in half.
- Combine with a heuristic function to turn it into A* search when I have domain knowledge about direction.
Common Mistakes
- Forgetting to skip already-visited vertices during relaxation, which can cause incorrect updates.
- Using the algorithm on graphs with negative edge weights and getting silently wrong answers.
- Not handling disconnected graphs, where some vertices remain at infinity — I need to check for that before treating the output as valid.
- Off-by-one errors when initializing distances, especially forgetting to set the source distance to zero.
- Confusing “shortest path” with “path with fewest edges” — Dijkstra optimizes total weight, not hop count.
Further Reading
- Dijkstra, E. W. (1959). “A note on two problems in connexion with graphs.” Numerische Mathematik, 1, 269–271.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- GeeksforGeeks, Dijkstra’s Algorithm: https://www.geeksforgeeks.org/dsa/dijkstras-shortest-path-algorithm-greedy-algo-7/
- Stanford CS161 lecture notes on shortest paths: https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/
