Сигнал задачи
Когда применять
Нужно минимизировать стоимость цепочки переходов.
Что держать в голове
- Уметь вычислять расстояния в невзвешенном графе.
- Уметь инициализировать multi-source BFS несколькими вершинами расстояния 0.
Сложность
- BFS для невзвешенного графа: O(V + E); Дейкстра с двоичной кучей и неотрицательными весами: O((V + E) log V).
Границы и ошибки
- Алгоритм выбирают по модели веса: обычный BFS не учитывает разные стоимости, а Дейкстра некорректен при отрицательных рёбрах.