Dijkstra’s algorithm explained step by step

The problem

You have a weighted graph: vertices joined by edges, each edge carrying a length or cost $w(u, v) \ge 0$. The length of a path is the sum of its edge weights. Given a source vertex $s$, the single-source shortest-path problem asks for the shortest distance $\delta(s, v)$ to every vertex $v$, and a path that achieves it.

If every edge had weight 1, breadth-first search would solve this: it visits vertices in order of their number of edges from $s$. Dijkstra’s algorithm, published by Edsger Dijkstra in 1959, generalises BFS to weighted edges. It replaces BFS’s first-in, first-out queue with a priority queue that always hands back the closest vertex not yet finished.

The idea in one paragraph

Keep a tentative distance $d[v]$ for every vertex, starting at 0 for the source and $\infty$ for everything else. Repeatedly pick the unfinished vertex with the smallest tentative distance and declare that distance final: the vertex is settled. Then relax each edge leaving it: if going through $u$ gives a neighbour $v$ a shorter route than any known so far, lower $d[v]$ and remember $u$ as $v$’s parent:

When every reachable vertex is settled, $d$ holds the shortest distances, and the parent pointers form a shortest-path tree.

Try it

The visualiser opens on a small road map, searching from S. Step forwards with → and watch the priority queue, the distance table and the highlighted pseudocode. Then drag vertices, change weights or draw your own graph; the run restarts automatically.

Pseudocode

This is the version most real programs use, with a binary-heap priority queue and “lazy deletion”: when a vertex’s distance improves, a new entry is pushed, and outdated entries are skipped when they come out.

dijkstra(G, s):
    for each vertex v: d[v] ← ∞; parent[v] ← none
    d[s] ← 0
    PQ ← min-priority queue containing (0, s)
    while PQ is not empty:
        (dist, u) ← extract-min(PQ)
        if u is settled: continue        // a stale entry
        mark u settled
        for each edge (u, v) with weight w:
            if d[u] + w < d[v]:
                d[v] ← d[u] + w
                parent[v] ← u
                insert (d[v], v) into PQ
    return d, parent

Rebuilding the path

Dijkstra’s algorithm records only one parent per vertex, but that is enough to recover every shortest path. To find the route to $t$, start at $t$, follow parent back to the source, and reverse the list. This costs time proportional to the number of edges on the path. If you only need the route to a single target, you can stop the main loop as soon as the target is settled; its distance is already final at that point.

Why it is correct

The whole algorithm rests on one claim: when a vertex is taken from the queue, its tentative distance is already the true shortest distance. Here is why, using the fact that weights are non-negative.

As a corollary, vertices are settled in non-decreasing order of distance, as the “Settle” column of the worked example shows: 0, 2, 5, 9, 10, 13.

Negative edges break it

The proof used non-negative weights in one place: the step that says the rest of the path cannot be shorter than nothing. With a negative edge, a vertex can be settled too early. In this directed graph the edges are S → A (2), S → B (4), B → A (-3), A → C (2).

Dijkstra settles A at 2 straight away, because 2 is the smallest tentative distance. Only later does it settle B and see the edge B → A, which gives $4 - 3 = 1$. A is already settled, so the improvement is ignored, and C inherits the error. You can reproduce this in the visualiser: tick “Directed”, enter the edges as text, and it will warn you about the negative weight.

For graphs with negative edges, use the Bellman–Ford algorithm. It relaxes every edge $V - 1$ times, in $O(VE)$ time, and can also detect a negative cycle, a loop with negative total weight, around which there is no shortest path at all. In many applications, though, negative weights never arise: distances, times and costs are non-negative by nature.

Running time

Every vertex is settled once, and every edge is relaxed at most once in each direction. What changes is how the priority queue is implemented:

With lazy deletion the heap can hold up to $E$ entries rather than $V$, but since $\log E \le 2\log V$ the bound is the same. On the road map, the algorithm made 9 insertions and 9 extractions for 6 vertices and 9 edges. Road networks and most real graphs are sparse, which is why the binary-heap version is the standard one.

Dijkstra, A* and friends

• BFS is Dijkstra with every weight equal to 1, where a plain queue already delivers vertices in distance order.
• A* search adds a heuristic $h(v)$, an estimate of the remaining distance to the target, and orders the queue by $d[v] + h(v)$ instead of $d[v]$. With a heuristic that never overestimates, such as straight-line distance on a map, it still finds the shortest path but explores far fewer vertices. Dijkstra is A* with $h = 0$.
• Prim’s algorithm for minimum spanning trees has almost identical code; it keys the queue by the weight of the single connecting edge rather than the total distance from the source.
• Route planners run Dijkstra-based algorithms on graphs with millions of vertices, with precomputation such as contraction hierarchies so a query touches only a tiny part of the map.

References

1. E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik 1, 269–271, 1959. doi:10.1007/BF01386390
2. M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms”, Journal of the ACM 34(3), 1987. doi:10.1145/28869.28874
3. P. E. Hart, N. J. Nilsson and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths”, IEEE Transactions on Systems Science and Cybernetics 4(2), 1968. doi:10.1109/TSSC.1968.300136
4. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. Chapter 22, “Single-source shortest paths”.