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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник