Я читал о алгоритмах Graph, и я наткнулся на эти два алгоритма.
Я много искал об этом, но не получил удовлетворительного ответа!
У меня есть сомнения, что в чем разница между алгоритмом Дейкстры и BFS при поиске кратчайшего пути?
при использовании BFS для нахождения кратчайшего пути в графе, что мы делаем,
Мы обнаруживаем все связанные вершины, добавляем их в очередь и поддерживаем расстояние от источника к этой вершине. Теперь, если мы найдем путь от источника к этой вершине с еще меньшим расстоянием, тогда мы его обновим!
Это то же самое, что мы делаем в алгоритме Дейкстры! то в чем разница между Dijkstra и BFS? И тогда почему временные сложности этих алгоритмов отличаются друг от друга?
Если кто-нибудь может объяснить это с помощью псевдокода, тогда я буду очень благодарен!
Я знаю, что чего-то не хватает! Пожалуйста помоги!
Первый поиск по ширине - это просто алгоритм Дейкстры со всеми весами ребер, равными 1.
Алгоритм Дейкстра представляет собой концептуально широкий поиск, который учитывает краевые издержки.
Процесс изучения графа в обоих случаях структурно одинаковый.
Blockquote при использовании BFS для нахождения кратчайшего пути в графике, что мы делаем Мы обнаруживаем все связанные вершины, добавляем их в очередь, а также поддерживаем расстояние от источника до этой вершины. Теперь, если мы найдем путь от источника к этой вершине с еще меньшим расстоянием, тогда мы его обновим!
Мы не поддерживаем дистанцию в BFS. Это для обнаружения узлов. Поэтому мы помещаем их в общую очередь и всплываем. в отличие от Dijikstra, где мы кладем накопительный вес node (после релаксации) в очереди приоритетов и выходим на минимальное расстояние.
Таким образом, BFS будет работать как dijikstra в графе равного веса, потому что.
сложность варьируется из-за использования простой очереди и очереди приоритетов.