How Dijkstra's algorithm finds the shortest path
A plain guide to the shortest-path method behind route planners and internet routing, how it settles one place at a time, and where it stops working.
Written by Amili, an AI writer, from the sources listed below · 8 October 2026 · 6 min read
Dijkstra's algorithm finds the cheapest route from one starting point to every other point in a network whose connections have non-negative costs. It repeatedly settles the closest unsettled point, which makes it the backbone of route planning and of internet routing protocols such as OSPF and IS-IS.
In short
- It works on a graph: places are nodes, connections are edges, and each edge carries a cost such as distance.
- It always expands the unsettled node with the smallest known distance, so each settled distance is final.
- It needs costs that are zero or positive; negative costs call for Bellman–Ford instead.
- A priority queue makes it fast, and it runs inside routing protocols, map services and other algorithms.
What problem does Dijkstra's algorithm solve?
Many everyday questions are really questions about networks. Which roads give the quickest drive across a country? Which chain of routers should a data packet pass through? In each case there is a set of locations, a set of links between them, and a cost attached to every link. Mathematicians call this structure a weighted graph, and the task of finding the cheapest route through it is called the shortest path problem.
Dijkstra's algorithm answers a broad version of that question. Given one starting node, it works out the cheapest total cost to reach every other node, along with the route that achieves it. If only one destination matters, the method can simply stop as soon as that destination is settled. The Dutch computer scientist Edsger W. Dijkstra came up with it in 1956 and published it in 1959.
How does it work, step by step?
The method begins with pessimism. Every node is given a tentative distance of infinity, meaning no route to it is known yet, except the starting node, which gets zero. All nodes start out in an unvisited pool.
Next, it picks the unvisited node with the smallest tentative distance and treats it as the current node. For each neighbour of that node, it adds the current distance to the cost of the connecting edge. If that sum beats the neighbour's existing figure, the neighbour's distance is lowered and the current node is recorded as the step that leads there. This update is often called relaxation.
When every neighbour has been checked, the current node leaves the pool and is never examined again. That is safe because no cheaper route to it can still be hiding: any other path would have to pass through a node that is already at least as far away, and costs never go down along a path. The loop repeats until the pool is empty or only unreachable nodes remain. Following the recorded predecessor links backwards from any node then traces its shortest route.
What does a worked example look like?
Imagine five towns: A, B, C, D and E. Roads run from A to B costing 4, A to C costing 1, C to B costing 2, B to D costing 1, C to D costing 6, and D to E costing 3. Start at A.
A is settled at 0. Its neighbours get provisional values: B becomes 4 and C becomes 1. The smallest unsettled value is C, so C is settled at 1. Through C, B could be reached for 1 plus 2, which is 3, an improvement on 4, so B drops to 3. D gets 1 plus 6, which is 7. Now B is the smallest at 3 and is settled. Through B, D costs 3 plus 1, which is 4, beating 7. D is settled at 4, and finally E gets 4 plus 3, which is 7.
Notice what happened along the way. The direct road from A to B looked attractive at first, but the detour through C turned out cheaper. The algorithm never commits to a guess until the guess is provably the best available, which is why it can correct early impressions without backtracking.
Where is it used?
The most visible use is turn-by-turn directions in web mapping services, where roads become edges weighted by length or travel time. Behind the scenes, internet routing protocols such as Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS) rely on it to decide how traffic should move between routers. It also appears as a building block inside larger methods, such as Johnson's algorithm for finding shortest paths between every pair of nodes.
In artificial intelligence the same idea appears under the name uniform cost search, a member of the broader family of best-first search. Because a graph can describe states and moves rather than places and roads, shortest-path methods can also find the fewest moves needed to reach a goal state in a puzzle such as a Rubik's Cube.
Where does it fail or get misused?
The key assumption is that edge costs are never negative. If a link could reduce the running total, a node that was settled early might later turn out to have a cheaper route, and the algorithm's guarantee collapses. For graphs with negative weights, the Bellman–Ford algorithm is the standard choice.
Speed is the other limit. The simplest version scans every node to find the next one to settle, which grows slowly on large networks. Using a min-priority queue helps a great deal, and in 1984 Fredman and Tarjan showed that a Fibonacci heap brings the running time down to the best known bound for general directed graphs with non-negative weights. For huge road networks, services often go further: methods such as contraction hierarchies preprocess the map and can answer queries up to seven orders of magnitude faster. When a good estimate of the remaining distance exists, the A* search algorithm uses that hint to explore fewer nodes.
What does it teach about thinking?
Dijkstra said he designed the method in roughly twenty minutes at a café in Amsterdam, and that working without pencil and paper pushed him to strip out needless complexity. He built it to show off the new ARMAC computer at the Mathematical Center in Amsterdam, running it on a simplified map of 64 Dutch cities so that each city number fitted in 6 bits.
The broader lesson is about certainty. The algorithm only locks in a conclusion once nothing cheaper can possibly remain, and until then it keeps every estimate open to revision. Treating early figures as provisional, and settling the most certain thing first, is a habit that transfers well beyond graphs.
Questions people ask
Is Dijkstra's algorithm greedy?
Yes. At each step it makes the locally best choice by settling the unvisited node with the smallest known distance. Unlike many greedy methods, this choice is provably correct as long as no edge has a negative cost, because nothing settled later can offer a cheaper route back to a node that is already settled. That guarantee is what makes the approach both simple and reliable.
What is the difference between Dijkstra's algorithm and A*?
Both search outward from a start node, but A* adds an estimate of how far each node is from the target. That estimate steers the search toward the goal, so it often examines fewer nodes when only one destination matters. Dijkstra's algorithm uses no such hint and computes distances to every reachable node, which is useful when many destinations are needed at once.
Why can't Dijkstra's algorithm handle negative weights?
The method assumes that once a node is settled, no later path can reach it more cheaply. A negative edge breaks that promise, because a route that looks longer at first could become cheaper after crossing it. The settled value would then be wrong. The Bellman–Ford algorithm handles negative weights by repeatedly relaxing every edge, at the cost of more work.
The thinking behind it
It introduces graph search and Dijkstra's algorithm with illustrated, beginner-friendly examples.
Read or listen to Grokking Algorithms
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Dijkstra's algorithm — Wikipedia
- Shortest path problem — Wikipedia
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.