Key takeaways
- Dijkstra's algorithm finds the shortest distance from one start vertex to every other vertex in a graph with nonnegative edge weights.
- Repeatedly finalise the unvisited vertex with the smallest tentative distance, then update its neighbours' tentative distances.
- Record each vertex's predecessor when its distance improves, so the shortest route can be traced back at the end.
- It is correct because, with nonnegative weights, no later route can undercut the smallest tentative distance.
- Negative edge weights break that reasoning, so Dijkstra's algorithm can give wrong answers on graphs that have them.
A recurring graph question is the shortest route from one place to every other place. For graphs whose edge weights are distances, times or costs that cannot be negative, a standard method is Dijkstra's algorithm. Sedgewick and Wayne's Algorithms describes it as solving the single-source shortest-paths problem in edge-weighted graphs with nonnegative weights.
The idea
Grow a set of vertices whose shortest distance is known for certain, starting from the source. At each step, the next vertex to finalise is the one with the smallest tentative distance among those not yet final. Then use it to improve the tentative distances of its neighbours, an operation usually called relaxing its edges.
The example graph
Undirected, with these weights:
| Edge | SA | SB | AB | AC | BC | BD | CD | CT | DT |
|---|---|---|---|---|---|---|---|---|---|
| Weight | 4 | 2 | 1 | 5 | 8 | 10 | 2 | 6 | 2 |
Goal: shortest distances from S to every vertex, and the shortest route from S to T.
Step by step
Start with distance 0 at S and ∞ everywhere else. Each row shows the tentative distances after the vertex in the first column is finalised and its edges relaxed; a value in brackets is the predecessor that produced it.
| Finalise | S | A | B | C | D | T |
|---|---|---|---|---|---|---|
| Start | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| S (0) | 0 | 4 (S) | 2 (S) | ∞ | ∞ | ∞ |
| B (2) | 3 (B) | 2 | 10 (B) | 12 (B) | ∞ | |
| A (3) | 3 | 8 (A) | 12 (B) | ∞ | ||
| C (8) | 8 | 10 (C) | 14 (C) | |||
| D (10) | 10 | 12 (D) | ||||
| T (12) | 12 |
Notes on the key steps:
- After S: A gets 4 and B gets 2. B is smaller, so B is finalised next.
- After B: going S → B → A costs 2 + 1 = 3, which beats 4, so A improves to 3 with predecessor B. C gets 2 + 8 = 10 and D gets 2 + 10 = 12.
- After A: S → B → A → C costs 3 + 5 = 8, beating 10.
- After C: D improves to 8 + 2 = 10, beating 12; T gets 8 + 6 = 14.
- After D: T improves to 10 + 2 = 12.
Final distances from S: A = 3, B = 2, C = 8, D = 10, T = 12.
Recovering the route
Follow the predecessors back from T: T came from D, D from C, C from A, A from B, B from S. So the shortest route is
S → B → A → C → D → T, with length 2 + 1 + 5 + 2 + 2 = 12.
The predecessor links for all vertices together form a shortest-path tree rooted at S: every vertex hangs from the vertex that last improved it.
Notice the direct-looking route S → A → C → T has length 4 + 5 + 6 = 15. The algorithm found a route with more edges and less total weight, which is the whole point of weighting.
Why it is correct
When a vertex u is chosen, it has the smallest tentative distance among all unfinished vertices, say d. Any other route to u must leave the finished set at some point, through an unfinished vertex whose tentative distance is already at least d, and then continue along edges whose weights are nonnegative. So that route has length at least d, and d is truly the shortest. A formal version of this argument is an induction on the number of finalised vertices.
The word nonnegative in that argument is essential. Sedgewick and Wayne restrict attention to nonnegative weights for exactly this reason.
What goes wrong with negative weights
Take three vertices: S–A with weight 2, S–B with weight 3, and a directed edge B → A with weight −2. Dijkstra finalises A at distance 2 first, since 2 < 3. But the route S → B → A has length 3 + (−2) = 1, shorter, and it is discovered too late. Graphs with negative weights need other algorithms, such as Bellman–Ford, which Sedgewick and Wayne also present.
Dijkstra versus a minimum spanning tree
Both algorithms grow a tree greedily, and both look alike on paper, but they optimise different things. Dijkstra's tree minimises the distance from the source to each vertex. A minimum spanning tree minimises the total weight of the whole network. A triangle shows the difference: vertices S, A and B with SA = 2, SB = 2 and AB = 1. The minimum spanning tree is AB plus one of the 2-edges, total weight 3. Dijkstra's tree from S uses SA and SB, total weight 4, because that puts both A and B at distance 2, while the spanning tree would leave one of them at distance 3. Prim's algorithm and Dijkstra's differ in a single line: Prim compares the weight of the edge alone, Dijkstra compares the distance from the source.
How fast is it?
With a priority queue to find the smallest tentative distance, Sedgewick and Wayne show the running time grows in proportion to E log V in the worst case, for E edges and V vertices; see big-O notation for what that means. Storing the graph as adjacency lists, covered in adjacency matrices and lists, keeps the relaxation step efficient.
Run it yourself
Run the algorithm from A on the example graph. (Distances: B 1, S 3, C 5, D 7, T 9.) Then add an edge S–T of weight 11 and run it from S again. Does the route to T change?
MathWorld describes the algorithm as constructing a shortest-path tree from the initial vertex to every other vertex, and Applied Discrete Structures sets weighted graphs among other graph optimisation problems such as the travelling salesman problem and maximum flow. Graphs belong to the graph theory unit of Discrete Math: Study & Quiz. Find it with our education apps, and the full graph sequence in the discrete math hub, beginning with graph theory basics.
Good to know
Frequently asked questions
What does Dijkstra's algorithm do?
How do you run Dijkstra's algorithm by hand?
Why doesn't Dijkstra's algorithm work with negative weights?
Is Dijkstra's shortest-path tree the same as a minimum spanning tree?
Sources
- Shortest Paths (Algorithms, 4th edition, Sedgewick and Wayne) (opens in a new tab)Princeton University — accessed
- Dijkstra's Algorithm (opens in a new tab)Wolfram MathWorld — accessed
- Graph Optimization (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.