Warum den Dijkstra-Algorithmus verwenden, wenn Breadth First Search (BFS) dasselbe schneller ausführen kann?

Beide können verwendet werden, um den kürzesten Weg aus einer Hand zu finden. BFS läuft ein O(E+V), während Dijkstra einläuft O((V+E)*log(V)).

Außerdem habe ich gesehen, dass Dijkstra ähnlich wie in Routing-Protokollen verwendet wird.

Warum also den Dijkstra-Algorithmus verwenden, wenn BFS dasselbe schneller kann?

Mit Dijkstra können Sie jedem Schritt andere Entfernungen als 1 zuweisen. Beim Routing können die Entfernungen (oder Gewichte) beispielsweise nach Geschwindigkeit, Kosten, Präferenz usw. zugewiesen werden. Der Algorithmus gibt Ihnen dann den kürzesten Weg von Ihrer Quelle zu jedem Knoten im durchquerten Diagramm.

In der Zwischenzeit erweitert BFS die Suche bei jeder Iteration im Grunde genommen nur um einen „Schritt“ (Link, Kante, wie auch immer Sie sie in Ihrer Anwendung nennen möchten), was dazu führt, dass die kleinste Anzahl von Schritten gefunden wird, die erforderlich sind , um zu einem Schritt zu gelangen gegebener Knoten von Ihrer Quelle ("root").

Wenn Sie Reisewebsites in Betracht ziehen, verwenden diese den Dijkstra-Algorithmus aufgrund von Gewichten (Entfernungen) auf Knoten.

Wenn Sie den gleichen Abstand zwischen allen Knoten berücksichtigen, ist BFS die bessere Wahl.

Betrachten Sie zum Beispiel A -> (B, C) -> (F)mit Kantengewichten gegeben durch A->B= 10, A->C= 20, B->F= C->F= 5.

Wenn wir hier BFS anwenden, lautet die Antwort ABF oder ACF, da beide kürzeste Wege sind (in Bezug auf die Anzahl der Kanten). Wenn wir jedoch Dijstra anwenden, lautet die Antwort nur ABF, da die Gewichte auf der Verbindung berücksichtigt werden Pfad.

Dijkstras Algorithmus

• Wie BFS für gewichtete Diagramme.
• Wenn alle Kosten gleich sind, ist Dijkstra = BFS

Quelle: https://cs.stanford.edu/people/abisee/gs.pdf

Aus Sicht der Implementierung könnte der Dijkstra-Algorithmus genau wie ein BFS implementiert werden, indem der queuemit einem ausgetauscht wird priority queue.

Quelle