Ujemne wagi z wykorzystaniem algorytmu Dijkstry

Próbuję zrozumieć, dlaczego algorytm Dijkstry nie będzie działał z ujemnymi wagami. Czytając przykład na Shortest Paths , próbuję rozgryźć następujący scenariusz:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

Ze strony internetowej:

Zakładając, że wszystkie krawędzie są skierowane od lewej do prawej, jeśli zaczniemy od A, algorytm Dijkstry wybierze krawędź (A, x) minimalizując d (A, A) + długość (krawędź), czyli (A, B). Następnie ustawia d (A, B) = 2 i wybiera inną krawędź (y, C) minimalizując d (A, y) + d (y, C); jedynym wyborem jest (A, C) i ustala d (A, C) = 3. Ale nigdy nie znajduje najkrótszej ścieżki z A do B, przez C, o łącznej długości 1.

Nie mogę zrozumieć, dlaczego przy użyciu następującej implementacji Dijkstry, d [B] nie zostanie zaktualizowany do 1(Kiedy algorytm osiągnie wierzchołek C, uruchomi relaksację na B, zobacz, że d [B] jest równe 2, a zatem zaktualizuje jego wartość do 1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ← Ø
   Q ← V[G]//priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v  V(G)
      d[v] ← ∞
      π[v] ← NIL
   d[s] ← 0
}

Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      π[v] ← u
      Update(Q, v)
}

Dzięki,

Meir

Algorytm, który zasugerowałeś, rzeczywiście znajdzie najkrótszą ścieżkę na tym wykresie, ale ogólnie nie wszystkie wykresy. Na przykład rozważ ten wykres:

Załóżmy, że krawędzie są skierowane od lewej do prawej, jak w twoim przykładzie,

Twój algorytm będzie działał w następujący sposób:

1. Najpierw ustaw d(A)na, zeroa pozostałe odległości na infinity.
2. Następnie rozwijasz węzeł A, ustawiając d(B)na 1, d(C)na zeroi d(D)na 99.
3. Następnie rozszerzasz się Cbez zmian netto.
4. Następnie rozszerzasz się B, co nie ma żadnego efektu.
5. Wreszcie rozszerzasz D, co zmienia się d(B)na -201.

Zauważ, że na końcu tego jednak d(C)jest to nadal 0, mimo że najkrótsza ścieżka Cma długość -200. W niektórych przypadkach algorytm nie jest w stanie dokładnie obliczyć odległości. Co więcej, nawet gdybyś miał przechowywać wskaźniki wstecz mówiące o tym, jak dostać się z każdego węzła do węzła początkowego A, skończyłbyś wybierając niewłaściwą ścieżkę z powrotem Cdo A.

Zauważ, że Dijkstra działa nawet dla wag ujemnych, jeśli wykres nie ma cykli ujemnych, tj. Cykli, których sumaryczna waga jest mniejsza od zera.

Oczywiście można by zapytać, dlaczego w przykładzie stworzonym przez templatetypedef Dijkstra zawodzi, mimo że nie ma cykli ujemnych, a właściwie nawet cykli. Dzieje się tak, ponieważ używa innego kryterium zatrzymania, które utrzymuje algorytm, gdy tylko zostanie osiągnięty docelowy węzeł (lub wszystkie węzły zostaną raz ustalone, nie określił tego dokładnie). Na wykresie bez ujemnych wag działa to dobrze.

Jeśli używa się alternatywnego kryterium zatrzymania, które zatrzymuje algorytm, gdy kolejka priorytetowa (sterta) jest pusta (to kryterium zatrzymania zostało również użyte w pytaniu), to dijkstra znajdzie prawidłową odległość nawet dla wykresów z ujemnymi wagami, ale bez ujemne cykle.

Jednak w tym przypadku asymptotyczna granica czasu dijkstry dla grafów bez cykli ujemnych zostaje utracona. Dzieje się tak, ponieważ wcześniej ustalony węzeł można ponownie wstawić do sterty, gdy zostanie znaleziona lepsza odległość ze względu na ujemne wagi. Ta właściwość nazywa się poprawianiem etykiet.

nie użyłeś S nigdzie w swoim algorytmie (poza jego modyfikacją). idea dijkstry jest taka, że ​​gdy wierzchołek znajdzie się na S, nie będzie już nigdy modyfikowany. w takim przypadku, gdy B znajdzie się w S, nie dojdziesz do niego ponownie przez C.

fakt ten zapewnia złożoność O (E + VlogV) [w przeciwnym razie krawędzie zostaną powtórzone więcej niż raz, a wierzchołki więcej niż raz]

innymi słowy, algorytm, który opublikowałeś, może nie znajdować się w O (E + VlogV), zgodnie z obietnicą algorytmu Dijkstry.

Ponieważ Dijkstra jest podejściem Chciwym, gdy wierzchołek zostanie oznaczony jako odwiedzony w tej pętli, nigdy nie zostanie ponownie oszacowany, nawet jeśli istnieje inna ścieżka o mniejszym koszcie dotarcia do niego później. A taki problem może się zdarzyć tylko wtedy, gdy na wykresie istnieją krawędzie ujemne.

Zachłanny algorytm , jak sama nazwa wskazuje, zawsze dokonuje wyboru, który wydaje się być najlepszym w tej chwili. Załóżmy, że masz funkcję celu, która musi zostać zoptymalizowana (zmaksymalizowana lub zminimalizowana) w danym momencie. Algorytm Greedy dokonuje zachłannych wyborów na każdym kroku, aby zapewnić optymalizację funkcji celu. Algorytm Greedy ma tylko jedną szansę na obliczenie optymalnego rozwiązania, tak aby nigdy się nie cofał i nie cofał decyzji.

TL; DR: Odpowiedź zależy od implementacji. W przypadku opublikowanego pseudokodu działa on z wagami ujemnymi.

Warianty algorytmu Dijkstry

Kluczowe jest to, że istnieją 3 rodzaje implementacji algorytmu Dijkstry , ale wszystkie odpowiedzi na to pytanie ignorują różnice między tymi wariantami.

1. Użycie zagnieżdżonej forpętli do rozluźnienia wierzchołków. To najłatwiejszy sposób na wdrożenie algorytmu Dijkstry. Złożoność czasowa wynosi O (V ^ 2).
2. Implementacja oparta na kolejce priorytetowej / stercie + NIE zezwala się na ponowne wejście, gdzie ponowne wejście oznacza, że ​​zrelaksowany wierzchołek może zostać ponownie wepchnięty do kolejki priorytetowej, aby ponownie go rozluźnić później .
3. Dozwolone jest wdrażanie w oparciu o kolejkę priorytetową / stertę + ponowne wejście.

Wersja 1 i 2 zawiedzie na wykresach z ujemnymi wagami (jeśli w takich przypadkach uzyskasz poprawną odpowiedź, to tylko zbieg okoliczności), ale wersja 3 nadal działa .

Pseudokod przesłany w ramach oryginalnego problemu to wersja 3 powyżej, więc działa z ujemnymi wagami.

Oto dobra referencja z Algorithm (4. wydanie) , która mówi (i zawiera implementację Java wersji 2 i 3, o której wspomniałem powyżej):

P. Czy algorytm Dijkstry działa z ujemnymi wagami?

A. Tak i nie. Istnieją dwa algorytmy najkrótszych ścieżek, znane jako algorytm Dijkstry, w zależności od tego, czy wierzchołek może zostać umieszczony w kolejce priorytetowej więcej niż raz. Gdy wagi są nieujemne, obie wersje pokrywają się (ponieważ żaden wierzchołek nie zostanie kolejkowany więcej niż raz). Wersja zaimplementowana w DijkstraSP.java (która umożliwia kolejkowanie wierzchołka więcej niż jeden raz) jest poprawna w obecności ujemnych wag krawędzi (ale bez ujemnych cykli), ale w najgorszym przypadku jej czas wykonywania jest wykładniczy. (Zwracamy uwagę, że DijkstraSP.java zgłasza wyjątek, jeśli dwuznak ważony krawędzią ma krawędź o ujemnej wadze, więc programista nie jest zaskoczony tym wykładniczym zachowaniem). Jeśli zmodyfikujemy DijkstraSP.java tak, że wierzchołek nie może być kolejkowany więcej niż raz (np. używając oznaczonej tablicy [] do oznaczenia tych wierzchołków, które zostały rozluźnione),

Więcej szczegółów dotyczących implementacji i połączenia wersji 3 z algorytmem Bellmana-Forda można znaleźć w odpowiedzi z zhihu . To także moja odpowiedź (ale po chińsku). Obecnie nie mam czasu, aby przetłumaczyć to na angielski. Naprawdę doceniam, gdyby ktoś mógł to zrobić i edytować tę odpowiedź na stackoverflow.

Zastanów się, co się stanie, jeśli będziesz podróżować tam iz powrotem między B i C ... voila

(dotyczy tylko wtedy, gdy wykres nie jest skierowany)

Edytowano: Uważam, że problem polega na tym, że ścieżka z AC * może być lepsza niż AB tylko z istnieniem ujemnych krawędzi wagi, więc nie ma znaczenia, gdzie idziesz po AC, przy założeniu, że nie ujemne krawędzie wagi nie można znaleźć ścieżki lepszej niż AB, gdy zdecydowałeś się dotrzeć do B po przejściu na AC.

"2) Czy możemy użyć algorytmu Dijksry do najkrótszych ścieżek dla wykresów z wagami ujemnymi - jednym pomysłem może być obliczenie wartości minimalnej wagi, dodanie wartości dodatniej (równej wartości bezwzględnej wartości wagi minimalnej) do wszystkich wag i uruchomienie algorytmu Dijksry dla zmodyfikowanego wykresu. Czy ten algorytm zadziała? ”

To absolutnie nie działa, chyba że wszystkie najkrótsze ścieżki mają taką samą długość. Na przykład biorąc pod uwagę najkrótszą ścieżkę o długości dwóch krawędzi i po dodaniu wartości bezwzględnej do każdej krawędzi, całkowity koszt ścieżki jest zwiększany o 2 * | max waga ujemna |. Z drugiej strony kolejna ścieżka o długości trzech krawędzi, więc koszt ścieżki jest zwiększony o 3 * | max ujemna waga |. W związku z tym wszystkie różne ścieżki są zwiększane o różne kwoty.

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.