Czy algorytm Dijkstry to tylko BFS z kolejką priorytetową?

22

Według tej strony algorytm Dijkstry to po prostu BFS z kolejką priorytetową. Czy to naprawdę takie proste? Myślę, że nie.

algorithms graphs shortest-path Barry Fruitman
źródło

1

Dlaczego tak myślisz

Raphael

@ Rafael Ponieważ wydaje się to zbyt proste i jest tak: ponownie przestudiowałem to i widzę, że teraz nie śledzi odległości między węzłami, więc to naprawdę BFS, a nie Dijkstra.

Barry Fruitman

1

Cóż, Dijkstra nie zmienia wartości, według których kolejka jest „sortowana” (często nazywana „relaksacją”); jeśli tego zabronisz, to nie to samo, prawda.

Raphael

20

Możesz zaimplementować algorytm Dijkstry jako BFS z kolejką priorytetową (choć nie jest to jedyna implementacja).

Algorytm Dijkstry polega na tym, że najkrótsza ścieżka od do jest również najkrótszą ścieżką do dowolnego z wierzchołków wzdłuż ścieżki. Właśnie to robi BFS. $s$ $t$

Lub z innej perspektywy: jak zachowałby się algorytm Dijkstry, gdyby wszystkie wagi były równe 1? Dokładnie jak BFS.

Shaull
źródło

4

Po pierwsze, jak możemy dostosować BFS do bardziej ogólnego wykresu ważonego ? $G = (V, E)$

Oto pomysł z książki „Algorytmy (sekcja 4.4)” Dasgupta i in .:

Dla każdej krawędzi z (o masie ) zastąpienie go krawędzi o długości dodając obojętne węzłów pomiędzy i . $e = (u,v)$ $E$ $l_e$ $l_e$ $1$ $l_e - 1$ $u$ $v$

W rezultacie wszystkie krawędzie wykresu wyników mają długość jednostkową. Dlatego możemy obliczyć odległości w , uruchamiając BFS na . $G'$ $G$ $G'$

Po drugie, w jaki sposób algorytm Dijkstry na pokonuje BFS na transformowanym grafie ? $G$ $G'$

BFS na może być naprawdę powolny, jeśli niektóre są duże, ponieważ marnuje zbyt dużo czasu na obliczanie odległości do tych fałszywych węzłów, o których w ogóle nie dbamy. Algorytm Dijkstry unika tego, ustawiając szacunkowe odległości dla węzłów i rozluźniając je w miarę możliwości. $G'$ $l_e$

Po trzecie, jak zachowuje się algorytm Dijkstry na nieważonych grafach?

Zachowuje się dokładnie tak samo jak BFS. Opracowujemy to z dwóch głównych punktów.

„Relaks”.

Dla algorytmu Dijkstry na ogólnym wykresie ważonym relaksacja wynosi
```
for all edges (u,v) in E:
    if dist(v) > dist(u) + w(u,v)
       dist(v) = dist(u) + w(u,v)
```
W przypadku BFS na nieważonym wykresie wiemy, że i , więc relaksacja jest prostsza: $dist(v) = \infty$ $w(u,v) = 1$
```
for all edges (u,v) in E:
    if dist(v) = \infty
       dist(v) = dist(u) + 1
```
W „kolejce priorytetowej”.

Gdy algorytm Dijkstry jest uruchamiany na nieważonym wykresie, kolejka priorytetowa zawiera co najwyżej dwie różne wartości (odległości). Dlatego wystarcza kolejka FIFO BFS.

hengxin
źródło

Czy algorytm Dijkstry to tylko BFS z kolejką priorytetową?

Odpowiedzi: