A routing feature uses BFS to find the "shortest" path between two warehouses in a graph, and it works correctly for months. Then a new requirement adds travel times to the edges, and the same BFS starts returning wrong answers on some routes while still looking like it's finding *a* path. What broke, and what's the actual fix?

BFS finds the shortest path only under one specific condition that's easy to forget once it's been true for months: every edge has to cost the same. BFS works by exploring everything one hop away, then everything two hops away, and so on — so the first time it reaches a vertex is guaranteed to be by the fewest possible hops, which is the same thing as "shortest" exactly when every hop costs the same amount. Once edges carry different travel times, a two-hop path can be cheaper than a one-hop path, and BFS has no way to know that — it still finds a valid path, just not necessarily the cheapest one, because it never compares costs, only hop counts. The fix is Dijkstra's algorithm, which is structurally the same walk as BFS with one change: instead of a plain queue that always takes the oldest-discovered vertex next, it uses a priority queue that always takes the cheapest-so-far vertex next, which is what actually accounts for the weights.