Dlaczego algorytm Dijkstry nie działa dla krawędzi o ujemnej wadze?

121

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.

Madu
źródło
3
Prawidłowa odpowiedź z dobrym przykładem to: stackoverflow.com/questions/6799172/…
Amitk

Odpowiedzi:

175

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:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

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).

dobrze
źródło
5
Przepraszamy, ale nie pojawia się żaden błąd. Najpierw A->Bbędzie 5, a A->Cpotem 2. Potem B->Cbędzie -5. Więc wartość Cwill będzie taka -5sama jak bellman-ford. Dlaczego to nie daje właściwej odpowiedzi?
Anirban Nag 'tintinmj'
5
@tintinmj najpierw, Dijkstra „zamknie” węzeł Az wartością 0. Następnie będzie szukał węzła o minimalnej wartości, Bto 5 i C2. Minimalna wartość to C, więc zamknie się Cz wartością 2 i nigdy nie obejrzy się wstecz, kiedy później Bjest zamknięty, nie może zmienić wartości C, ponieważ jest już „zamknięty”.
rano
4
@amit Jak algorytm Dijkstry nie znajdzie ścieżki A -> B -> C? Najpierw zaktualizuje Codległość do 2, a następnie Bodległość do 5. Zakładając, że na twoim wykresie nie ma żadnych krawędzi wychodzących z C, wtedy nic nie robimy podczas wizyty C(a odległość nadal wynosi 2). Następnie odwiedzamy Dsąsiednie węzły, a jedynym sąsiednim węzłem jest C, 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 z C, otrzymasz rodzica B, a następnie uzyskasz Apoprawny wynik. czego mi brakuje?
nbro
12
@amit Problem z twoim rozumowaniem (tak mi się wydaje), i widziałem, jak robią to inni ludzie (co dziwne), polega na tym, że myślisz, że algorytm nie rozważy ponownie węzłów, których najkrótsza odległość została już określona (i już skończyliśmy), ale to nie jest poprawne i dlatego mamy krok "relaksacji" ... Iterujemy przez wszystkie węzły wykresu i dla każdego z nich iterujemy przez sąsiednie węzły, nawet jeśli którykolwiek z sąsiednich węzłów może zostały już na przykład usunięte z naszej kolejki o minimalnym priorytecie.
nbro
10
@amit Sprawdź odpowiedź na podobne pytanie, gdzie przykład rzeczywiście ma sens: stackoverflow.com/a/6799344/3924118
nbro
37

Rozważ poniższy wykres ze źródłem jako wierzchołkiem A. Najpierw spróbuj samodzielnie uruchomić na nim algorytm Dijkstry.

wprowadź opis obrazu tutaj

Kiedy w swoim wyjaśnieniu odnoszę się do algorytmu Dijkstry, będę mówić o algorytmie Dijkstry zaimplementowanym poniżej,

Algorytm Dijkstry

Na początku wartości ( odległość od źródła do wierzchołka ) początkowo przypisane do każdego wierzchołka to:

inicjalizacja

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,

pierwsza iteracja

Teraz wyodrębniamy C jako (2 <5), teraz Q = [B] . Zauważ, że C nie jest do niczego podłączony, więc line16pętla nie działa.

druga iteracja

Na koniec wyodrębniamy B, po czym Q to Phi. Uwaga B ma skierowaną krawędź do C, ale C nie występuje w Q, dlatego ponownie nie wprowadzamy pętli for line16,

3rd?

Więc otrzymujemy odległości jako

bez zmian chłopaki

Zwróć uwagę, że jest to błędne, ponieważ najkrótsza odległość od A do C wynosi 5 + -10 = -5, kiedy jedziesz od a do b do c.

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 line16robi 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 line16sprawdzają sąsiadami v (to jest skierowany od krawędzi istnieje u do v ), w U , które są jeszcze w Q . W line14usuwają odwiedzane notatki z Q. Więc jeśli x jest odwiedzanym sąsiadem u , ścieżka nieźródło do u do x 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 A do B do Cnie została uwzględniona, pozostawiając aktualną najkrótszą ścieżkę A do Cbez 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 - niemożliwektó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 13najpierw 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.

Zatem wszelkie obliczenia dist [x], które wykonamy, będą nieprawidłowe, jeśli x zostanie usunięte, zanim wszystkie wierzchołki v - takie, że x jest sąsiadem v z łączącą je ujemną krawędzią - zostaną usunięte.

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.

Aditya P
źródło
2
Jak powiedziałeś, lepszym sposobem rozwiązania tego problemu jest użycie metody heapq.heappush po każdym porównaniu. Przesuwamy zaktualizowaną odległość do kolejki. Pod tym warunkiem Dijkstra może pracować na ujemnych wagach. Próbowałem i wynik wyszedł jako 0,5, -5
nosense
1
"źródło ścieżki do x do u nie jest nawet brane pod uwagę"; czy miałeś na myśli źródło u do x?
slmatrix
1
@slmatrix dzięki za złapanie tego, tak, miałem na myśli, że ścieżka od źródła do u do x, ponieważ x jest sąsiadem u.
Aditya P
23

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.

zmbq
źródło
8

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.

Nikunj Banka
źródło
6

Wypróbuj algorytm Dijkstry na poniższym wykresie, zakładając, że Ajest to węzeł źródłowy, aby zobaczyć, co się dzieje:

Wykres

tb-
źródło
6
Przepraszamy, ale nie pojawia się żaden błąd. Pierwsza A->Bwola 1i A->Cwola 100. Wtedy B->Dbędzie 2. Wtedy C->Dbędzie -4900. Więc wartość Dwill będzie taka -4900sama jak bellman-ford. Dlaczego to nie daje właściwej odpowiedzi?
Anirban Nag 'tintinmj'
9
@tintinmj Jeśli masz krawędź wychodzącą z D, zostanie ona odwiedzona, zanim odległość D zostanie zmniejszona, a zatem nie zostanie zaktualizowana po jej zakończeniu. To z pewnością spowoduje błąd. Jeśli weźmiesz D 2 jako ostateczną odległość już po zeskanowaniu wychodzących krawędzi, nawet ten wykres daje błąd.
Christian Schnorr,
@ tb- Przepraszam, że pytam po tak długim czasie, ale czy jestem na dobrej drodze? Najpierw A->Bbędzie 1i A->Cbędzie 100. Następnie Bjest badany i ustawiany B->Dna 2. Następnie badane jest D, ponieważ obecnie ma najkrótszą drogę powrotną do źródła? Czy miałbym rację, mówiąc, że gdyby B->Dbył 100, Czostałby zbadany jako pierwszy? Rozumiem wszystkie inne przykłady, z wyjątkiem twojego.
Pejman Poh
@PejmanPoh z mojego rozumienia, jeśli B-> D wynosi 100, ponieważ A-> C jest wyższe w HeapStructure, która będzie używana, wyciąg min zwróci najpierw A-> C, co oznacza, że ​​następną znalezioną najkrótszą ścieżką będzie ścieżka do C, po tym ścieżka z C-> D o wadze -5000 będzie oczywistym wyborem, co prowadzi nas do wniosku, że najkrótsza ścieżka prowadziłaby z A-> C-> D i jestem prawie pewien, że tak być normalnym zachowaniem. Więc czasami, gdy mamy cykle ujemne, nadal możemy uzyskać właściwą wartość dla najkrótszej ścieżki, ale na pewno nie zawsze, jest to przykład, w którym nie będziemy ...
T.Dimitrov
1

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.

winorośl
źródło
0

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:

A  <- 5 ->  B  <- (-1) ->  C <- 5 -> D

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.

Dakkaron
źródło
0

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.

CodingLab
źródło