Po co używać algorytmu Dijkstry, skoro Breadth First Search (BFS) może zrobić to samo szybciej?

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?

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

• Podobnie jak BFS dla wykresów ważonych.
• Jeśli wszystkie koszty są równe, Dijkstra = BFS

Źródło: https://cs.stanford.edu/people/abisee/gs.pdf

Z punktu widzenia implementacji algorytm Dijkstry można zaimplementować dokładnie tak, jak BFS, zamieniając queueplik priority queue.

Źródło