Obie można użyć do znalezienia najkrótszej ścieżki z jednego źródła. BFS działa w O (E + V), podczas gdy Dijkstra działa w O ((V + E) * log (V)).Dlaczego warto korzystać z algorytmu Dijkstry, jeśli funkcja Szerokie pierwsze wyszukiwanie (BFS) może zrobić to samo szybciej?
Ponadto widziałem, że Dijkstra używane było bardzo podobnie do protokołów routingu.
W związku z tym, dlaczego warto zastosować algorytm Dijkstry, jeśli BFS może zrobić to samo szybciej?
Dijkstra umożliwia przypisanie odległości innych niż 1 dla każdego kroku. Na przykład w routingu odległości (lub ciężary) mogą być przypisane przez prędkość, koszt, preferencje itp. Następnie algorytm podaje najkrótszą ścieżkę ze źródła do każdego węzła na wykresie.
Tymczasem BFS zasadzie tylko rozszerza wyszukiwanie według jednego „Step” (link, EDGE, co chcesz to nazwać w aplikacji) na każdej iteracji, co zdarza się mieć wpływ na znalezieniu najmniejszej liczbę kroków wystarczy, aby dostać się do dowolnego węzła ze źródła ("root").
Jeśli weźmiesz pod uwagę witryny podróżnicze, używają one algorytmu Dijkstry z powodu wag (odległości) na węzłach.
Jeśli weźmiesz pod uwagę tę samą odległość między wszystkimi węzłami, wówczas lepszym wyborem będzie BFS.
Na przykład, rozważmy A -> (B, C) -> (F) z ciężarkami brzegowych podanych przez A->B = 10, A->C = 20, B->F = C->F = 5.
Tutaj, jeśli zastosujemy BFS, odpowiedź będzie ABF lub ACF, ponieważ oba są najkrótsze ścieżki (w odniesieniu do liczby krawędzi), ale jeśli zastosujemy Dijstę, odpowiedź będzie ABF tylko dlatego, że rozważa wagi na połączonej ścieżce.
Obie dadzą takie same wyniki, tj. Ścieżkę między dwoma wierzchołkami, ale tylko dijkstra zagwarantuje najkrótszą ścieżkę. – Edwin
Zobacz zaakceptowaną odpowiedź, drugi komentarz. Bardzo dobry sposób wyjaśnienia, dlaczego złożoność obliczeniowa jest inna: https://stackoverflow.com/questions/25449781/what-is-difference-between-bfs-and-dijkstras-algorithms-when-looking-for-shorte – jmcarter9t