Oba mogą być użyte do znalezienia najkrótszej ścieżki z jednego źródła. BFS wbiega O(E+V), a Dijkstra wbiega O((V+E)*log(V)).
Poza tym widziałem, że Dijkstra używał bardzo podobnie jak w protokołach routingu.
Zatem po co używać algorytmu Dijkstry, skoro BFS może zrobić to samo szybciej?
Odpowiedzi:
Dijkstra umożliwia przypisanie odległości innych niż 1 dla każdego kroku. Na przykład w trasowaniu odległości (lub wagi) można przypisać na podstawie prędkości, kosztu, preferencji itp. Algorytm następnie podaje najkrótszą ścieżkę od źródła do każdego węzła na przemierzanym wykresie.
W międzyczasie BFS po prostu rozszerza wyszukiwanie o jeden „krok” (link, brzeg, jakkolwiek chcesz to nazwać w swojej aplikacji) w każdej iteracji, co zdarza się mieć efekt znalezienia najmniejszej liczby kroków potrzebnych do dotarcia do dowolnego dany węzeł z twojego źródła („root”).
Jeśli weźmiesz pod uwagę witryny turystyczne, używają one algorytmu Dijkstry ze względu na wagi (odległości) w węzłach.
Jeśli weźmiesz pod uwagę tę samą odległość między wszystkimi węzłami, lepszym wyborem będzie BFS.
Na przykład rozważmy A -> (B, C) -> (F)z wagami krawędzi podanymi przez A->B= 10, A->C= 20, B->F= C->F= 5.
Tutaj, jeśli zastosujemy BFS, odpowiedzią będzie ABF lub ACF, ponieważ obie są najkrótszymi ścieżkami (pod względem liczby krawędzi), ale jeśli zastosujemy Dijstrę, odpowiedzią będzie ABF tylko dlatego, że uwzględnia wagi na podłączonych ścieżka.
Algorytm Dijkstry