~11 min · graph-algorithms, weighted, shortest-path
Level 0Curious Beginner
0 XP0/85 lessons0/19 achievements
0/100 XP to next level100 XP to go0% complete
"BFS treats every road as one step. But a real map has short streets and long highways — and the moment edges carry different costs, 'fewest roads' stops meaning 'shortest trip.'"
Edges Grow Numbers
A weighted graph attaches a number to each edge: a distance, a travel time, a price, a bandwidth, a probability. Suddenly the question 'what's the shortest path?' has a richer answer — it's the path with the lowest total weight, not the fewest edges. In an adjacency list, you just store the weight alongside the neighbor: {"A": [("B", 5), ("C", 1)], ...}. The graph structure is the same; each edge now carries a cost.
Why This Breaks BFS
BFS finds the path with the fewest edges, which is correct only when all edges cost the same. Picture this: A→B is a single road of length 100, while A→C→D→B is three short roads totaling 6. BFS, counting hops, declares A→B the 'shortest' at one edge — and sends you on the 100-unit detour. The fewest-edges path and the lowest-cost path have diverged. To handle weights, you need an algorithm that accumulates total cost and always expands the cheapest-so-far frontier node next. That's Dijkstra, and it's built on the priority queue from the Heaps track — the structure for 'always give me the current cheapest.'
A weighted graph puts a cost on each edge, so the shortest path is the one with the lowest TOTAL weight — not the fewest edges. BFS (which counts hops) is wrong here; weighted shortest paths need cost-aware algorithms like Dijkstra, powered by a priority queue.
The Family of Weighted Problems
Weights open a whole family of classic problems, and this track tours the essential ones:
Single-source shortest path: cheapest route from one start to everywhere. Dijkstra (non-negative weights) or Bellman-Ford (handles negatives) — next two lessons.
Connectivity: union-find, for 'are these connected?' and as a building block.
Minimum spanning tree: cheapest way to connect everything — Kruskal and Prim.
All-pairs shortest path (Floyd-Warshall): cheapest route between every pair — a name to know, though we won't implement it here.
Every one of these is 'optimize over a weighted network,' and together they cover routing, network design, scheduling, and clustering — an enormous slice of real systems.
Pippa's Confession
I once used BFS to route between two points on a weighted map and got a path that was technically 'two hops' but went the long way around — a highway when a few side streets were shorter. Dad pointed at the weights I'd been ignoring: "BFS is counting roads, not miles." The fix wasn't a smarter BFS; it was a different algorithm entirely (Dijkstra) that adds up the miles. Choosing fewest-edges when I meant lowest-cost was a category error, and weights are exactly where that error bites.
Code
Fewest edges is not cheapest cost·python
# A weighted graph: store (neighbor, weight) in the adjacency list.
weighted = {
"A": [("B", 100), ("C", 2)],
"C": [("D", 2)],
"D": [("B", 2)],
"B": [],
}
# By FEWEST EDGES (what BFS finds): A -> B, just 1 hop... but cost 100.
# By LOWEST COST (what we actually want): A -> C -> D -> B, 3 hops, cost 6.
def path_cost(graph, path):
total = 0
for u, v in zip(path, path[1:]):
total += dict(graph[u])[v] # weight of edge u->v
return total
print("A->B (fewest edges):", path_cost(weighted, ["A", "B"])) # 100
print("A->C->D->B (cheapest):", path_cost(weighted, ["A", "C", "D", "B"])) # 6
# BFS would pick the 1-edge path (cost 100). The cheapest path has MORE edges.
# That's why weighted graphs need Dijkstra, not BFS.
On a weighted graph, you have edges A→B (cost 10), A→C (cost 3), C→B (cost 3). Find the fewest-edges path from A to B and its cost, then the lowest-cost path and its cost. Which would BFS return, and why is that the wrong answer when edges represent, say, travel time?
Hint
Fewest edges: A→B, 1 hop, cost 10. Lowest cost: A→C→B, 2 hops, cost 6. BFS returns A→B (one hop) — wrong when you care about total travel time, because the two-hop route is actually faster. Weighted = sum costs, not count hops.
Progress
Progress is local-only — sign in to sync across devices.