Why doesn't breadth-first search give the cheapest path once the links have different costs?

Breadth-first search, the ring walk, counts links, not costs, so it can return the one-link route that costs 120 minutes while a two-link route costs 25. It is not broken. It is answering how few links, and once links have different costs that is no longer the same question as how little time or money.

Take three towns. The first has a direct road to the third taking 120 minutes. It also has a road to the second taking 10 minutes, and the second has a road to the third taking 15 minutes. The direct route uses one link. The route through the second uses two links and costs $10+15=25$ minutes. Breadth-first search meets the third town through the direct road at depth one and marks it visited. It therefore never considers the two-link route, even though that route is cheaper by $120-25=95$ minutes.

The natural guess is that fewer hops must mean less cost. That guess is exactly what breadth-first search encodes. Its waiting line is served in arrival order, so the first time it reaches a town it fixes the smallest number of links to that town. A later route with two links and total 25 arrives after the one-link route with total 120, and the visited mark prevents the 25 from replacing the 120. The problem is not that breadth-first search is careless with the costs. It does not look at the costs at all.

The repair is one substitution. Keep a best known cost for every town, zero at the start and infinity elsewhere. Take from the waiting line the town with the smallest best known cost, not the one that joined first. For each neighbour, test whether the cost through the current town is lower than the best known cost, and if it is, record the lower cost and put the neighbour in the line. This is the same walk as before except that the line is ordered by cost rather than by arrival.

At the second step the route to b is already known at 4, from a directly. Going through c costs $1+2=3$, so the 4 is replaced by 3. That replacement is the part breadth-first search has no equivalent of. A town can enter the line more than once before it is finally settled, and the stale entry is ignored when it surfaces. At the end the costs are a 0, c 1, b 3, d 7, e 9. The route to d through c costs $1+6=7$; the route to d through b costs $3+4=7$, so it does not improve. The route to e through d costs $7+2=9$.

When a town $v$ comes out of the line as the cheapest, at cost $c$, the method declares it settled. Suppose a later route reached $v$ more cheaply. That route must leave the settled region through some town $u$ still in the line, because $v$ is outside the settled region until now. Since $v$ was the cheapest in the line, $\text{cost}(u) \ge c$. The rest of the route from $u$ to $v$ has total link cost $w$, so it costs $\text{cost}(u)+w$. If every link cost is nonnegative then $w \ge 0$, hence $\text{cost}(u)+w \ge c$. No later route can be cheaper.