Можно ли BFS-ом искать кратчайший путь при весах рёбер 1..k и стоит ли?
Веса рёбер — небольшие целые числа от 1 до, скажем, 10. Можно ли обойтись без Дейкстры? Думал «разбить» тяжёлое ребро на несколько единичных и пустить обычный BFS. Это рабочий приём или есть подвох?
2 ответа
Да, приём рабочий: ребро веса w заменяем цепочкой из w рёбер веса 1 через w-1 фиктивных вершин. Тогда обычный BFS даёт кратчайший путь. Но подвох — в размере графа: число вершин раздувается до O(V + сумма всех весов). При больших весах это взрывается по памяти.
Лучший вариант для малых весов — dial's algorithm (BFS с k+1 корзинами / maxW-bucket queue): храним отдельные очереди для каждого возможного значения dist mod (maxW+1), обрабатываем по возрастанию.
// 0-1 BFS обобщается; для весов 1..W держим W+1 deque-ов
// или одну очередь приоритетов «вручную» по корзинам
Сложность dial's — O(V·maxW + E), что при маленьком maxW быстрее Дейкстры (нет log). Дробление на единичные рёбра работает, но безопасно лишь при суммарно небольших весах.
Практический совет: если maxW мал (до ~10) и граф большой — dial's или 0-1 BFS (для весов 0/1) реально выигрывают у Дейкстры по константе. Но если веса большие или произвольные — не выдумывайте, берите обычную Дейкстру O(E log V), она почти всегда проходит. Дробление рёбер оправдано только когда сумма весов гарантированно мала (например, веса до 3 и рёбер 10^5 → максимум ~3·10^5 доп. вершин — нормально).