🎓 A1Learner
🔍

DSA Why BFS Stops Working on Weighted Graphs

A weighted graph is a graph where each edge carries a cost. Breadth-first search counts hops, so its first arrival can miss the cheapest route.

Two routes with different prices

The direct edge costs 10 for one hop. The two-hop detour costs 1 plus 1.

direct = 10
detour = 1 + 1
print("direct", direct)
print("detour", detour)

BFS arrives by hops first

A queue visits the direct neighbour before the detour finishes. Hop order puts node B first here.

from collections import deque
graph = {"A": ["B", "C"], "B": [], "C": ["B"]}
seen = ["A"]
queue = deque(["A"])
while queue:
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in seen:
            seen.append(nxt)
            queue.append(nxt)
print(seen)

Example

from collections import deque

graph = {"A": ["B", "C"], "B": [], "C": ["B"]}
weights = {("A", "B"): 10, ("A", "C"): 1, ("C", "B"): 1}

order = ["A"]
queue = deque(["A"])
while queue:
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in order:
            order.append(nxt)
            queue.append(nxt)
print("BFS order:", order)
print("direct route cost:", weights[("A", "B")])
print("detour route cost:", weights[("A", "C")] + weights[("C", "B")])
print("cheapest route: A -> C -> B")

Key points

  • An edge weight is the cost of using one edge
  • A hop is one edge crossed, whatever its cost
  • Breadth-first search settles nodes in hop order on any graph
  • A cheap route can use more hops than a pricey route
  • The cheapest route minimises total weight, not hop count

In this example, breadth-first search reaches B in one hop from A. That arrival looks final under the unweighted rule from the Beginner course. Pricing both routes breaks the rule. The direct route costs 10 while the detour through C costs 2. The next lesson gives the algorithm that settles nodes by price.

Note

On unweighted graphs every weight is one, so hop order and price order agree.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Why does BFS fail on this weighted graph?