TL;DR:
A graph is a set of nodes joined by edges. Weights on the edges can stand for distance, time or cost.
Dijkstra's algorithm finds the cheapest route from one start node to every other node when all weights are non-negative.
It repeatedly settles the unsettled node with the smallest known distance, then checks whether going through it improves its neighbours.
Your phone finds a route between two places by treating the map as a puzzle: towns are points, roads join them, and each road has a length. Finding the shortest route is a classic graph problem, and one short algorithm solves it. We will trace it by hand on a tiny map so every step is visible.
The idea in plain words
A graph is made of nodes (also called vertices) and edges that connect pairs of nodes. If each edge has a number on it, such as a distance in kilometres, the graph is weighted. A path is a chain of edges from one node to another, and its cost is the sum of the weights along it.
The shortest path is the path with the smallest total cost. It is not necessarily the one with the fewest edges. A road with three short segments can beat a single long one.
How Dijkstra's algorithm thinks
Start with distance 0 at the start node and infinity everywhere else. Then repeat: pick the unsettled node with the smallest known distance and settle it, meaning its distance is now final. Look at each neighbour and ask: is going through the settled node cheaper than the best route found so far? If yes, update that neighbour's distance.
Settling is safe because every other route to that node must pass through a node that is at least as far away, and adding more non-negative weights can only make it longer. That is why the algorithm needs non-negative weights.
Worked example: a five-town map
Towns A to E, with these roads (distances in km): A to B is 4, A to C is 2, B to C is 1, B to D is 5, C to D is 8, C to E is 10 and D to E is 2. Find the shortest distance from A to every town.
After settling | A | B | C | D | E |
|---|---|---|---|---|---|
Start | 0 | ∞ | ∞ | ∞ | ∞ |
A (distance 0) | 0 | 4 | 2 | ∞ | ∞ |
C (distance 2) | 0 | 3 | 2 | 10 | 12 |
B (distance 3) | 0 | 3 | 2 | 8 | 12 |
D (distance 8) | 0 | 3 | 2 | 8 | 10 |
E (distance 10) | 0 | 3 | 2 | 8 | 10 |
Settle A. Via A: B = 0 + 4 = 4 and C = 0 + 2 = 2.
Settle C (smallest unsettled, 2). Via C: B = 2 + 1 = 3, which beats 4. D = 2 + 8 = 10. E = 2 + 10 = 12.
Settle B (3). Via B: D = 3 + 5 = 8, which beats 10.
Settle D (8). Via D: E = 8 + 2 = 10, which beats 12.
Settle E (10). Nothing is left to improve.
The final distances from A are: B = 3, C = 2, D = 8, E = 10. To rebuild the route to E, remember which neighbour improved each value last. E was set via D, D via B, B via C, and C via A. So the shortest path is A → C → B → D → E.
Check by adding the roads: 2 + 1 + 5 + 2 = 10. Compare some alternatives. A → C → E is 2 + 10 = 12. A → B → D → E is 4 + 5 + 2 = 11. A → C → D → E is 2 + 8 + 2 = 12. All are longer than 10.
The route with the fewest roads, A → C → E, has only two edges but costs 12. The cheapest route has four edges and costs 10. So counting edges is not the same as finding the shortest path.
The same trace in code
A short Python version keeps the graph in a dictionary and always picks the closest unsettled town. It is written for clarity, not speed.
roads = {
"A": {"B": 4, "C": 2},
"B": {"A": 4, "C": 1, "D": 5},
"C": {"A": 2, "B": 1, "D": 8, "E": 10},
"D": {"B": 5, "C": 8, "E": 2},
"E": {"C": 10, "D": 2},
}
dist = {town: float("inf") for town in roads}
dist["A"] = 0
unsettled = set(roads)
while unsettled:
here = min(unsettled, key=lambda t: dist[t])
unsettled.remove(here)
for nxt, km in roads[here].items():
if dist[here] + km < dist[nxt]:
dist[nxt] = dist[here] + km
print(dist)It prints {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}, the same distances as the hand trace. The dictionary roads lists each town's neighbours, so a road from B to C appears under both B and C.
How to check your answer
Add up the edge weights along your claimed path. It must equal the distance in your table.
Try two or three other routes and confirm none is cheaper.
Every settled distance should be no smaller than the one settled before it, since the algorithm settles in increasing order: 0, 2, 3, 8, 10.
Make sure every town ends with a finite distance. If one is still infinity, it is not connected.
Common mistakes
Updating a neighbour with only the edge weight, not the distance so far plus the edge weight.
Settling a node that does not have the smallest tentative distance.
Treating the shortest path as the one with the fewest edges.
Using the algorithm with negative weights, where settling is no longer safe.
Forgetting that a road works both ways in an undirected graph.
Where you will use it next
Graphs model maps, networks, social connections and dependencies. Dijkstra's algorithm is the base of many route finders, although real systems add extra tricks for speed. To store which node connects to which, programmers often use dictionaries, as in hash tables and why lookups are fast, and wrap the data in classes and objects in plain words.
Frequently asked questions
What if two paths tie?
Either is a shortest path. Dijkstra's algorithm returns one of them, depending on how ties are broken.
Is there a version for unweighted graphs?
Yes. Breadth-first search finds the path with the fewest edges, which is the shortest path when every edge counts as 1.
Get started
