Weighted Graphs
When steps aren't equal.
On a real map, roads have different lengths. The route with the fewest roads isn't always the shortest drive. When edges have weights, breadth first search isn't enough. We need Dijkstra's algorithm.

- Roads have lengths
- Fewest roads isn't shortest
- Enter Dijkstra
A map with distances
We store a weighted graph as a dictionary of dictionaries. Each place maps its neighbours to the distance. From home, the shop is four minutes away directly. But going through the park, it's only one plus two, three minutes. Run it.
roads = {
"Home": {"Shop": 4, "Park": 1},
"Park": {"Shop": 2, "School": 6},
"Shop": {"School": 3, "Library": 7},
"School": {"Library": 1},
"Library": {},
}
for place, links in roads.items():
print(f"{place:<8}", links)Home {'Shop': 4, 'Park': 1}
Park {'Shop': 2, 'School': 6}
Shop {'School': 3, 'Library': 7}
School {'Library': 1}
Library {}Dijkstra's idea
Dijkstra's algorithm always explores the closest unexplored place next. It starts with home at distance zero. It takes the nearest place, and checks whether going through it gives a shorter route to its neighbours. If so, it updates them. A heap makes finding the nearest place fast.
Summary
Weighted graphs need Dijkstra's algorithm, which always explores the nearest place next. Next, writing it in code.
Key takeaways- Edges have weights
- Fewest edges ≠ shortest
- Explore the nearest first