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

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.

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

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 line16pę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 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 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 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.

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.

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.

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

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.

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.

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.