Зачем использовать алгоритм Дейкстры, если width First Search (BFS) может сделать то же самое быстрее?
оба могут быть использованы для поиска кратчайшего пути из одного источника. BFS работает в O(E+V), в то время как Дейкстра работает в O((V+E)*log(V)).
кроме того, я видел, что Дейкстра используется много, как в протоколах маршрутизации.
таким образом, Зачем использовать алгоритм Дейкстры, если BFS может сделать то же самое быстрее?
3 ответов:
Dijkstra позволяет назначать расстояния, отличные от 1 для каждого шага. Например, при маршрутизации расстояния (или веса) могут быть назначены скоростью, стоимостью, предпочтениями и т. д. Алгоритм дает кратчайший путь от источника до каждого узла в графе проходится.
между тем BFS в основном просто расширяет поиск на один "шаг" (ссылка, край, все, что вы хотите назвать в своем приложении) на каждой итерации, которая, как правило, имеет эффект поиска наименьшего число шагов нужно, чтобы добраться до любого узла из исходного ("корень").
если вы рассматриваете туристические веб-сайты, они используют алгоритм Дейкстры из-за весов (расстояний) на узлах.
если вы будете рассматривать одинаковое расстояние между всеми узлами, то BFS является лучшим выбором.
рассмотрим, например,
A -> (B, C) -> (F)с весами ребер, заданнымиA->B= 10,A->C= 20,B->F=C->F= 5.здесь, если мы применяем BFS, ответ будет ABF или ACF, так как оба являются кратчайшими путями (по количеству ребер), но если мы примените Dijstra, ответ будет ABF только потому, что он учитывает веса на связном пути.
Comments