Кратчайший путь в графе с весами 0 и 1: чем обычный BFS здесь плох
В ориентированном графе веса рёбер бывают только 0 и 1, нужны кратчайшие расстояния от старта по сумме весов.
Разработчик решил, что «весов почти нет», и взял обычный BFS: расстояние до соседа считается как расстояние до текущей вершины плюс вес ребра, вершина помечается при первом попадании в очередь.
Граф: A -> B вес 1, A -> C вес 0, C -> B вес 0. Соседи A перебираются в порядке B, C. Такой BFS выдаёт dist['B'] == 1, хотя правильный ответ 0.
Что верно?
- BFS корректен при любых неотрицательных весах, а ошибка здесь только в порядке перебора соседей A
- Такую задачу за O(V + E) решить нельзя: при любых весах нужна Дейкстра с кучей и множителем log V
- Достаточно перебирать соседей по возрастанию веса ребра, и обычная очередь начнёт давать минимум
- Первое попадание в очередь здесь не даёт минимума суммы весов; выручает 0-1 BFS на deque