Dijkstra's algorithm
Dijkstra's algorithm finds the shortest distance from one node to every other when links have non-negative weights: settle the closest node, improve its neighbors, repeat.
Settle the closest unsettled node, then improve its neighbors
BFS finds the fewest hops, but when links have different lengths, the route with fewest hops can be the slow one. Dijkstra's algorithm finds the shortest distance from one start node to every other node in a weighted graph whose weights are never negative.
It grows a set of settled nodes, whose shortest distance is final. Each round it takes the unsettled node with the smallest known distance, settles it, and tries every link out of it: if going through it gives a neighbor a shorter distance than the best one known, the neighbor's distance drops. That update is called relaxation: a link u → v of weight w is relaxed by checking whether dist[u] + w beats dist[v].
Taking the closest node each round is a greedy choice, and a priority queue makes it fast: entries of [distance, node], always handing back the smallest.
The rule
With no negative weights, the unsettled node with the smallest known distance can't be reached any faster: every other route to it goes through a node that is at least as far. Settle it, relax its links, repeat.
Each round settles one node and relaxes its links
Place 3 was first queued at 6, then improved to 5 through place 1. The heap can't easily change an entry, so the new one is simply added and the old [6, 3] is skipped when it comes out. That skip, called lazy deletion, is how most real implementations work.
Read the problem as shortest distances from one source
A signal spreading through a network reaches each node at that node's shortest distance from the source, because it takes every link at once. So the time until all nodes have it is the largest of the shortest distances, and a node never reached means −1. The links are one-way here, and the nodes are numbered from 1, so the graph is a map.
The same algorithm works for any cost that never decreases along a route
Here a route's cost isn't a sum: it is the steepest single step on it. Dijkstra's algorithm still works, because extending a route can never make its cost smaller. Each cell is a node, its neighbors are the cells next door, and relaxing a step uses max(effort so far, this step's climb) instead of a sum.
This version recognizes an out-of-date entry by comparing it with the best known effort instead of keeping a settled set; both work. The winning route goes down the left side and along the bottom, heights 1, 2, 3, 4, 6, 5, never changing by more than 2, and the search stops as soon as the target is settled.
Negative weights break it, and the cost depends on the queue
The proof that a settled node is final assumes no link subtracts. With a negative link, a node settled early could later be reached more cheaply by a route through a node still in the queue, and Dijkstra's algorithm would miss it. Graphs with negative weights need Bellman-Ford & Floyd-Warshall.
Priority queue | Cost | Best for |
|---|---|---|
Binary heap (lazy deletion) | O((n + m) log n) | Sparse graphs: the usual choice |
Plain array, scan for the minimum | O(n²) | Dense graphs, where m is close to n² |
None, all weights equal | O(n + m) with BFS | Unweighted graphs |
To recover the route itself, not just its length, store for each node the node it was last relaxed from; following those back from the target spells out the route in reverse.
3 questions
Remember this
- Dijkstra's algorithm settles the closest unsettled node each round, then relaxes its links.
- It needs non-negative weights; a settled distance is then final.
- With a binary heap and lazy deletion it costs O((n + m) log n).
- Any route cost that never decreases as the route grows, such as a maximum, works the same way.
Now solve some yourself
Only this topic 0 of 8 solved
- MediumThe route most likely to succeed
- MediumShortest routes from the first city
- MediumVisit nodes before they disappear
- HardA graph that answers shortest-route queries
- HardCheapest flight with one half-price ticket
- HardThe shortest path, printed
- HardNodes reachable when links are split into pieces
- HardTwo sources meeting at one destination
Mixed with topics you have practiced 0 unlocked
9 more once you have practiced Grid traversal, Dynamic programming: basics. Play one of its examples to the end and solve one of its problems to unlock them.
Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.
Next