When can BFS replace Dijkstra’s algorithm?

Deep dive

Dijkstra is the general shortest-path algorithm for non-negative weights (different costs), usually with a priority queue.

BFS is the special case where every edge cost is identical (typically 1). In that world, “shortest path” means “fewest edges”, and BFS explores nodes in increasing hop count.

Useful variants

• 0–1 BFS (weights in {0,1}): use a deque (0-weight edges to front, 1-weight to back) in O(V+E).
• Small integer weights: Dial’s algorithm (bucket queue).

Common pitfalls

• Using BFS on weighted graphs and expecting correct weighted distances.
• Mixing up “shortest by hops” vs “shortest by total weight”.