Алгоритм Дейкстры в двух словах — когда он вообще нужен?
Знаю BFS для поиска кратчайшего пути. Зачем тогда Дейкстра? В каких задачах BFS не справится и нужен именно он? Без вывода формул, просто суть.
3 ответа
Короткая суть: BFS находит кратчайший путь, когда все рёбра «весят» одинаково (одно ребро = один шаг). Как только у рёбер появляются разные веса (расстояния, время, цена), BFS уже не годится — он считает количество рёбер, а не сумму весов.
Дейкстра — это как раз поиск кратчайшего пути во взвешенном графе с неотрицательными весами. Он жадно на каждом шаге берёт ближайшую ещё не обработанную вершину (обычно через очередь с приоритетом / кучу) и обновляет расстояния до соседей.
Границы применимости: веса должны быть неотрицательными. Если есть отрицательные рёбра — Дейкстра ломается, там нужен Беллман–Форд.
Когда у рёбер разные веса. Для равных весов хватает BFS, веса разные — Дейкстра.
Когда у рёбер разные веса.
