Log in

Dijkstra's Algorithm Explained with a Step-by-Step Example

Last updated · Part of the Discretiq guides

Dijkstra's algorithm finds the shortest path from one starting vertex to every other vertex in a weighted graph, as long as no edge has a negative weight. It is the method behind many route planners and network routing protocols.

The idea is greedy: always finalise the closest vertex you have not finished yet, then use it to look for shortcuts to its neighbours.

How it works

  1. Give the start vertex distance 0 and every other vertex distance ∞.
  2. Pick the unfinished vertex with the smallest distance and mark it finalised.
  3. For each edge from it to a neighbour, relax the edge: if (its distance + the weight) is smaller than the neighbour's current distance, update the neighbour.
  4. Repeat steps 2 and 3 until every reachable vertex is finalised.

Worked example

Undirected graph with edges A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6, E–F 3. Start at A. Each row shows the distances after finalising the named vertex.

FinalisedABCDEF
A042∞∞∞
C0321012∞
B032812∞
D03281014
E03281013
F03281013

Notice what happened. The direct edge A–B has weight 4, but after finalising C the route A → C → B costs 2 + 1 = 3, so B improves. Later F is first reached at 14 through D, and then improves to 13 through E.

Following the parent links backwards gives the shortest route to F: A → C → B → D → E → F, total 2 + 1 + 5 + 2 + 3 = 13.

Why it is correct

When a vertex is finalised, its distance is the smallest of all unfinished vertices. Any other route to it must pass through some unfinished vertex that is already at least as far away, and adding more non-negative edges can only make the route longer. So no later discovery can improve it.

Why negative weights break it

That argument fails when an edge can reduce the total. Take directed edges A → B (2), A → C (3) and C → B (−2). Dijkstra finalises B at distance 2 before it ever examines C. But A → C → B costs 3 − 2 = 1, which is shorter. For graphs with negative weights use the Bellman–Ford algorithm instead.

Running time

With a binary heap as the priority queue, Dijkstra's algorithm runs in O((V + E) log V) time for V vertices and E edges. A plain array scan costs O(V²), which is fine for small dense graphs.

Common mistakes

  • Finalising a vertex because it was discovered first, rather than because its distance is currently smallest.
  • Forgetting to update a neighbour whose distance improves later (as B and F did above).
  • Using the algorithm on a graph with a negative edge.
  • Reading the distance table but not recording parent vertices, so the actual path is lost.
  • Treating an undirected edge as one-way. Relax it from both ends.

Frequently asked questions

Does Dijkstra's algorithm work on directed graphs?

Yes. Relax each edge only in its own direction.

What if some vertices are unreachable?

They keep distance ∞ and are reported as unreachable.

Is Dijkstra the same as BFS?

BFS finds shortest paths when every edge counts as 1. Dijkstra generalises that to different non-negative weights.

Try it yourself

Work the examples above by hand first, then confirm your answers.

Run Dijkstra's algorithm on your own graph

References and further reading

  • Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271.
  • Cormen, T., Leiserson, C., Rivest, R., Stein, C. Introduction to Algorithms. MIT Press.
  • Rosen, K. H. Discrete Mathematics and Its Applications. McGraw-Hill (standard undergraduate text).