AI Hints
Home›DSA in Python Tutorial›Weighted Graphs
DSA in Python · Lesson 82 of 132

Weighted Graphs

When steps aren't equal.

⏱ 2 min read▶ Video at 1:37:07🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Weighted Graphs
From the video: Weighted Graphs
  • 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.pypython
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)
Output
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.

Starthome = 0, others = ∞
Pickthe nearest unexplored place
Relaxshorter route via it? update
Heapfinds the nearest 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
Next up: Dijkstra's Algorithm — shortest routes with a heap