Czy ktoś może mi powiedzieć, dlaczego algorytm Dijkstry dla najkrótszej ścieżki z jednego źródła zakłada, że krawędzie muszą być nieujemne.
Mówię tylko o krawędziach, a nie o ujemnych cyklach wagi.
Czy ktoś może mi powiedzieć, dlaczego algorytm Dijkstry dla najkrótszej ścieżki z jednego źródła zakłada, że krawędzie muszą być nieujemne.
Mówię tylko o krawędziach, a nie o ujemnych cyklach wagi.
Odpowiedzi:
Przypomnijmy, że w algorytmie Dijkstry, gdy wierzchołek zostanie oznaczony jako „zamknięty” (i poza zbiorem otwartym) - algorytm znalazł do niego najkrótszą ścieżkę i nigdy nie będzie musiał ponownie rozwijać tego węzła - zakłada ścieżkę opracowaną do tego ścieżka jest najkrótsza.
Ale z ujemnymi wagami - może to nie być prawda. Na przykład:
Dijkstra z A najpierw opracuje C, a później nie znajdzie
A->B->C
EDYTUJ nieco głębsze wyjaśnienie:
Zauważ, że jest to ważne, ponieważ w każdym kroku relaksacji algorytm zakłada, że „koszt” dla „zamkniętych” węzłów jest rzeczywiście minimalny, a zatem węzeł, który zostanie wybrany jako następny, również jest minimalny.
Idea jest taka: jeśli mamy otwarty wierzchołek tak, że jego koszt jest minimalny - dodając dowolną liczbę dodatnią do dowolnego wierzchołka - minimalność nigdy się nie zmieni.
Bez ograniczenia liczb dodatnich - powyższe założenie nie jest prawdziwe.
Ponieważ „wiemy”, że każdy wierzchołek, który był „zamknięty”, jest minimalny - możemy bezpiecznie wykonać krok relaksacji - bez „oglądania się za siebie”. Jeśli musimy „spojrzeć wstecz” - Bellman-Ford oferuje rekurencyjne rozwiązanie (DP).
źródło
A->B
będzie 5, aA->C
potem 2. PotemB->C
będzie-5
. Więc wartośćC
will będzie taka-5
sama jak bellman-ford. Dlaczego to nie daje właściwej odpowiedzi?A
z wartością 0. Następnie będzie szukał węzła o minimalnej wartości,B
to 5 iC
2. Minimalna wartość toC
, więc zamknie sięC
z wartością 2 i nigdy nie obejrzy się wstecz, kiedy późniejB
jest zamknięty, nie może zmienić wartościC
, ponieważ jest już „zamknięty”.A -> B -> C
? Najpierw zaktualizujeC
odległość do 2, a następnieB
odległość do 5. Zakładając, że na twoim wykresie nie ma żadnych krawędzi wychodzących zC
, wtedy nic nie robimy podczas wizytyC
(a odległość nadal wynosi 2). Następnie odwiedzamyD
sąsiednie węzły, a jedynym sąsiednim węzłem jestC
, którego nowa odległość wynosi -5. Zwróć uwagę, że w algorytmie Dijkstry śledzimy również rodzica, z którego docieramy (i aktualizujemy) do węzła, a robiąc to zC
, otrzymasz rodzicaB
, a następnie uzyskaszA
poprawny wynik. czego mi brakuje?Rozważ poniższy wykres ze źródłem jako wierzchołkiem A. Najpierw spróbuj samodzielnie uruchomić na nim algorytm Dijkstry.
Kiedy w swoim wyjaśnieniu odnoszę się do algorytmu Dijkstry, będę mówić o algorytmie Dijkstry zaimplementowanym poniżej,
Na początku wartości ( odległość od źródła do wierzchołka ) początkowo przypisane do każdego wierzchołka to:
Najpierw wyodrębniamy wierzchołek w Q = [A, B, C], który ma najmniejszą wartość, tj. A, po czym Q = [B, C] . Uwaga A ma skierowaną krawędź do B i C, również oba są w Q, dlatego aktualizujemy obie te wartości,
Teraz wyodrębniamy C jako (2 <5), teraz Q = [B] . Zauważ, że C nie jest do niczego podłączony, więc
line16
pętla nie działa.Na koniec wyodrębniamy B, po czym . Uwaga B ma skierowaną krawędź do C, ale C nie występuje w Q, dlatego ponownie nie wprowadzamy pętli for
line16
,Więc otrzymujemy odległości jako
Zwróć uwagę, że jest to błędne, ponieważ najkrótsza odległość od A do C wynosi 5 + -10 = -5, kiedy jedziesz .
Więc dla tego wykresu Algorytm Dijkstry błędnie oblicza odległość od A do C.
Dzieje się tak, ponieważ Algorytm Dijkstry nie spróbować znaleźć krótszą drogę do wierzchołków, które są już wydobytych z Q .
To, co
line16
robi pętla, to bierze wierzchołek u i mówi „hej, wygląda na to, że możemy przejść do v ze źródła przez u , czy to (alternatywna lub alternatywna) odległość jest lepsza niż bieżąca odległość [v], którą mamy? Jeśli tak, zaktualizujmy dist [v] "Należy zauważyć, że
line16
sprawdzają sąsiadami v (to jest skierowany od krawędzi istnieje u do v ), w U , które są jeszcze w Q . Wline14
usuwają odwiedzane notatki z Q. Więc jeśli x jest odwiedzanym sąsiadem u , ścieżka nie jest nawet uważana za możliwą krótszą drogę od źródła do v .W naszym przykładzie powyżej C był odwiedzanym sąsiadem B, więc ścieżka nie została uwzględniona, pozostawiając aktualną najkrótszą ścieżkę bez zmian.
Jest to faktycznie przydatne, jeśli wszystkie wagi krawędzi są liczbami dodatnimi , ponieważ wtedy nie tracilibyśmy czasu na rozważanie ścieżek, które nie mogą być krótsze.
Mówię więc, że uruchamiając ten algorytm, jeśli x jest wyodrębniane z Q przed y , to nie jest możliwe znalezienie ścieżki - która jest krótsza. Pozwólcie, że wyjaśnię to na przykładzie,
Ponieważ y zostało właśnie wyodrębnione, a x zostało wyodrębnione przed sobą, to dist [y]> dist [x], ponieważ w przeciwnym razie y zostałoby wyodrębnione przed x . (
line 13
najpierw minimalna odległość)A jak już założyliśmy, że wagi krawędzi są dodatnie, tj. Długość (x, y)> 0 . Zatem alternatywna odległość (alt) przez y jest zawsze większa, tj. Odl [y] + długość (x, y)> odl [x] . Tak więc wartość dist [x] nie zostałaby zaktualizowana, nawet gdyby y był uważany za ścieżkę do x , dlatego dochodzimy do wniosku, że sensowne jest uwzględnienie tylko sąsiadów z y, którzy nadal znajdują się w Q (uwaga komentarz w
line16
)Ale to zależy od naszego założenia dodatniej długości krawędzi, jeśli długość (u, v) <0, to w zależności od tego, jak ujemna jest ta krawędź, możemy zastąpić dist [x] po porównaniu w
line18
.Ponieważ każdy z tych wierzchołków v jest przedostatnim wierzchołkiem na potencjalnej „lepszej” ścieżce od źródła do x , co jest odrzucane przez algorytm Dijkstry.
Więc w przykładzie, który podałem powyżej, błąd polegał na tym, że C zostało usunięte przed usunięciem B. Podczas gdy ten C był sąsiadem B z ujemną krawędzią!
Dla wyjaśnienia, B i C są sąsiadami A. B ma jednego sąsiada C, a C nie ma sąsiadów. długość (a, b) to długość krawędzi między wierzchołkami a i b.
źródło
Algorytm Dijkstry zakłada, że ścieżki mogą być tylko `` cięższe '', więc jeśli masz ścieżkę od A do B o wadze 3 i ścieżkę od A do C o wadze 3, nie ma możliwości dodania krawędzi i dostać się od A do B przez C o wadze mniejszej niż 3.
To założenie sprawia, że algorytm jest szybszy niż algorytmy, które muszą brać pod uwagę wagi ujemne.
źródło
Poprawność algorytmu Dijkstry:
Na każdym etapie algorytmu mamy 2 zestawy wierzchołków. Zbiór A składa się z wierzchołków, do których obliczyliśmy najkrótsze ścieżki. Zestaw B składa się z pozostałych wierzchołków.
Hipoteza indukcyjna : na każdym kroku zakładamy, że wszystkie poprzednie iteracje są poprawne.
Krok indukcyjny : Kiedy dodamy wierzchołek V do zbioru A i ustawimy odległość, która ma być odległa [V], musimy udowodnić, że ta odległość jest optymalna. Jeśli nie jest to optymalne, musi istnieć inna ścieżka do wierzchołka V, która ma krótszą długość.
Załóżmy, że ta inna ścieżka przechodzi przez jakiś wierzchołek X.
Teraz, ponieważ dist [V] <= dist [X], więc każda inna ścieżka do V będzie miała co najmniej odległość [V], chyba że wykres ma ujemne długości krawędzi.
Zatem, aby algorytm Dijkstry działał, wagi krawędzi muszą być nieujemne.
źródło
Wypróbuj algorytm Dijkstry na poniższym wykresie, zakładając, że
A
jest to węzeł źródłowy, aby zobaczyć, co się dzieje:źródło
A->B
wola1
iA->C
wola100
. WtedyB->D
będzie2
. WtedyC->D
będzie-4900
. Więc wartośćD
will będzie taka-4900
sama jak bellman-ford. Dlaczego to nie daje właściwej odpowiedzi?A->B
będzie1
iA->C
będzie100
. NastępnieB
jest badany i ustawianyB->D
na2
. Następnie badane jest D, ponieważ obecnie ma najkrótszą drogę powrotną do źródła? Czy miałbym rację, mówiąc, że gdybyB->D
był100
,C
zostałby zbadany jako pierwszy? Rozumiem wszystkie inne przykłady, z wyjątkiem twojego.Przypomnijmy, że w algorytmie Dijkstry, gdy wierzchołek jest oznaczony jako „zamknięty” (i poza zestawem otwartym) - zakłada, że każdy węzeł pochodzący z niego doprowadzi do większej odległości, więc algorytm znalazł najkrótszą ścieżkę do niego i będzie nigdy więcej nie trzeba rozwijać tego węzła, ale nie jest to prawdą w przypadku ujemnych wag.
źródło
Pozostałe odpowiedzi do tej pory dość dobrze pokazują, dlaczego algorytm Dijkstry nie radzi sobie z ujemnymi wagami na ścieżkach.
Ale samo pytanie może opierać się na złym zrozumieniu wagi ścieżek. Jeśli ujemne wagi na ścieżkach byłyby ogólnie dozwolone w algorytmach odnajdywania ścieżek, to otrzymywałbyś trwałe pętle, które się nie zatrzymały.
Rozważ to:
Jaka jest optymalna ścieżka między A i D?
Każdy algorytm znajdowania ścieżki musiałby w sposób ciągły zapętlać się między B i C, ponieważ zmniejszyłoby to wagę całej ścieżki. Zatem dopuszczenie ujemnych wag dla połączenia sprawi, że każdy algorytm odnajdywania ścieżki będzie wątpliwy, być może z wyjątkiem sytuacji, gdy ograniczysz każde połączenie do użycia tylko raz.
źródło
Możesz użyć algorytmu Dijkstry z ujemnymi krawędziami bez ujemnego cyklu, ale musisz pozwolić na wielokrotne odwiedzanie wierzchołka, a ta wersja straci swoją szybką złożoność czasową.
W takim przypadku praktycznie widziałem, że lepiej jest użyć algorytmu SPFA, który ma normalną kolejkę i radzi sobie z krawędziami ujemnymi.
źródło