В чем разница между алгоритмами BFS и Dijkstra при поиске кратчайшего пути?

Я читал о алгоритмах Graph, и я наткнулся на эти два алгоритма.

Я много искал об этом, но не получил удовлетворительного ответа!

У меня есть сомнения, что в чем разница между алгоритмом Дейкстры и BFS при поиске кратчайшего пути?

при использовании BFS для нахождения кратчайшего пути в графе, что мы делаем,

Мы обнаруживаем все связанные вершины, добавляем их в очередь и поддерживаем расстояние от источника к этой вершине. Теперь, если мы найдем путь от источника к этой вершине с еще меньшим расстоянием, тогда мы его обновим!

Это то же самое, что мы делаем в алгоритме Дейкстры! то в чем разница между Dijkstra и BFS? И тогда почему временные сложности этих алгоритмов отличаются друг от друга?

Если кто-нибудь может объяснить это с помощью псевдокода, тогда я буду очень благодарен!

Я знаю, что чего-то не хватает! Пожалуйста помоги!

Ответ 1

Первый поиск по ширине - это просто алгоритм Дейкстры со всеми весами ребер, равными 1.

Алгоритм Дейкстра представляет собой концептуально широкий поиск, который учитывает краевые издержки.

Процесс изучения графа в обоих случаях структурно одинаковый.

Ответ 2

Blockquote при использовании BFS для нахождения кратчайшего пути в графике, что мы делаем Мы обнаруживаем все связанные вершины, добавляем их в очередь, а также поддерживаем расстояние от источника до этой вершины. Теперь, если мы найдем путь от источника к этой вершине с еще меньшим расстоянием, тогда мы его обновим!

Мы не поддерживаем дистанцию в BFS. Это для обнаружения узлов. Поэтому мы помещаем их в общую очередь и всплываем. в отличие от Dijikstra, где мы кладем накопительный вес node (после релаксации) в очереди приоритетов и выходим на минимальное расстояние.

Таким образом, BFS будет работать как dijikstra в графе равного веса, потому что.

сложность варьируется из-за использования простой очереди и очереди приоритетов.