~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 numbers such as distance, time, price, capacity, or probability to edges. The path aggregation rule depends on the problem: costs may add, bandwidth may take a bottleneck minimum, and probabilities may multiply or be transformed with logarithms. A weight is not automatically an additive cost to minimize.
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.