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