Зачем использовать алгоритм Дейкстры, если поиск по ширине (BFS) может сделать то же самое быстрее?

Question

Оба могут быть использованы для поиска кратчайшего пути из одного источника. BFS работает в O(E+V), а Дейкстра работает в O((V+E)*log(V)).

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

Итак, зачем использовать алгоритм Дейкстры, если BFS может делать то же самое быстрее?

Answer 1

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

Между тем BFSв основном просто расширяет поиск на один «шаг» (ссылка, ребро, как бы вы ни называли его в вашем приложении) на каждой итерации, что приводит к нахождению наименьшего количества шагов , которое требуетсячтобы добраться до любого данного узла из вашего источника («корень»).

Answer 2

Если вы рассматриваете туристические сайты, они используют алгоритм Дейкстры из-за весов (расстояний) на узлах.

Если вы рассмотрите одинаковое расстояние между всеми узлами, то BFS - лучший выбор.

Например, рассмотрим A -> (B, C) -> (F) с весами ребер, заданными как A->B = 10, A->C = 20, B->F = C->F = 5.

Здесь, если мы применим BFS, ответом будет ABF или ACF, так как оба являются кратчайшими путями (относительно числа ребер), но если мы применим Dijstra, ответ будет ABF только потому, что он учитывает веса на подключенном пути.

Answer 3

Алгоритм Дейкстры

• Как BFS для взвешенных графиков.
• Если все затраты равны, Дейкстра = BFS

Источник: https://cs.stanford.edu/people/abisee/gs.pdf

Answer 4

С точки зрения реализации алгоритм Дейкстры может быть реализован точно так же, как BFS, если поменять queue на priority queue.

Источник: введите описание ссылки здесь