algorithm
Algorytm Bellmana-Forda

Uwagi

Algorytm najkrótszej ścieżki z jednego źródła (biorąc pod uwagę cykl ujemny na wykresie)

Przed przeczytaniem tego przykładu trzeba mieć krótki pomysł na relaksację krawędzi. Można nauczyć się go od tutaj

Algorytm Bellmana-Forda oblicza najkrótsze ścieżki od jednego wierzchołka źródłowego do wszystkich pozostałych wierzchołków w ważonym wykreślniku. Mimo że jest wolniejszy niż algorytm Dijkstry , działa w przypadkach, gdy waga krawędzi jest ujemna, a także wykrywa ujemny cykl wagowy na wykresie. Problem z Algorytmem Dijkstry polega na tym, że jeśli występuje cykl ujemny, ciągle przechodzisz przez cykl raz za razem i zmniejszasz odległość między dwoma wierzchołkami.

Algorytm ten polega na przejściu wszystkich krawędzi tego wykresu jeden po drugim w losowej kolejności. Może to być dowolna kolejność losowa. Ale musisz upewnić się, że jeśli uv (gdzie u i v są dwoma wierzchołkami na wykresie) jest jednym z twoich zamówień, to musi istnieć krawędź od u do v . Zwykle jest pobierany bezpośrednio z podanej kolejności danych wejściowych. Ponownie, każde losowe zamówienie będzie działać.

Po wybraniu zamówienia rozluźnimy krawędzie zgodnie z formułą relaksacyjną. Dla danej krawędzi UV przechodzącej od u do v formuła relaksacyjna jest następująca:

if distance[u] + cost[u][v] < d[v]
    d[v] = d[u] + cost[u][v]

Oznacza to, że jeśli odległość od źródła do dowolnego wierzchołka u + waga krawędzi uv jest mniejsza niż odległość od źródła do innego wierzchołka v , aktualizujemy odległość od źródła do v . Musimy rozluźnić krawędzie co najwyżej (V-1) razy, gdzie V jest liczbą krawędzi na wykresie. Dlaczego (V-1) pytasz? Wyjaśnimy to w innym przykładzie. Będziemy również śledzić wierzchołek nadrzędny dowolnego wierzchołka, to znaczy, gdy rozluźnimy krawędź, ustawimy:

parent[v] = u

Oznacza to, że znaleźliśmy inną krótszą ścieżkę do osiągnięcia v za pośrednictwem u . Będziemy potrzebować tego później, aby wydrukować najkrótszą ścieżkę od źródła do docelowego wierzchołka.

Spójrzmy na przykład. Mamy wykres:

Wybraliśmy 1 jako wierzchołek źródłowy . Chcemy znaleźć najkrótszą ścieżkę od źródła do wszystkich innych wierzchołków.

Na początku d [1] = 0, ponieważ jest to źródło. A odpoczynek to nieskończoność , ponieważ jeszcze nie znamy ich odległości.

Rozluźnimy krawędzie w tej sekwencji:

+--------+--------+--------+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |    4   |    5   |    6   |
+--------+--------+--------+--------+--------+--------+--------+
|  Edge  |  4->5  |  3->4  |  1->3  |  1->4  |  4->6  |  2->3  |
+--------+--------+--------+--------+--------+--------+--------+

Możesz wybrać dowolną sekwencję. Jeśli raz rozluźnimy krawędzie, co otrzymamy? Otrzymujemy odległość od źródła do wszystkich innych wierzchołków ścieżki, która wykorzystuje maksymalnie 1 krawędź. Teraz rozluźnijmy krawędzie i zaktualizuj wartości d [] . Otrzymujemy:

1. d [4] + koszt [4] [5] = nieskończoność + 7 = nieskończoność . Nie możemy zaktualizować tego.
2. d [2] + koszt [3] [4] = nieskończoność . Nie możemy zaktualizować tego.
3. d [1] + koszt [1] [2] = 0 + 2 = 2 < d [2] . Więc d [2] = 2 . Również rodzic [2] = 1 .
4. d [1] + koszt [1] [4] = 4 . Więc d [4] = 4 < d [4] . rodzic [4] = 1 .
5. d [4] + koszt [4] [6] = 9 . d [6] = 9 < d [6] . rodzic [6] = 4 .
6. d [2] + koszt [2] [2] = nieskończoność . Nie możemy zaktualizować tego.

Nie można zaktualizować niektórych wierzchołków, ponieważ warunek d[u] + cost[u][v] < d[v] nie jest zgodny. Jak powiedzieliśmy wcześniej, znaleźliśmy ścieżki od źródła do innych węzłów przy użyciu maksymalnie 1 krawędzi.

Nasza druga iteracja zapewni nam ścieżkę przy użyciu 2 węzłów. Otrzymujemy:

1. d [4] + koszt [4] [5] = 12 < d [5] . d [5] = 12 . rodzic [5] = 4 .
2. d [3] + koszt [3] [4] = 1 < d [4] . d [4] = 1 . rodzic [4] = 3 .
3. d [3] pozostaje niezmieniony.
4. d [4] pozostaje niezmieniony.
5. d [4] + koszt [4] [6] = 6 < d [6] . d [6] = 6 . rodzic [6] = 4 .
6. d [3] pozostaje niezmieniony.

Nasz wykres będzie wyglądał następująco:

Nasza trzecia iteracja zaktualizuje tylko wierzchołek 5 , gdzie d [5] będzie wynosić 8 . Nasz wykres będzie wyglądał następująco:

Po tym, bez względu na to, ile wykonamy iteracji, będziemy mieli te same odległości. Zachowamy więc flagę, która sprawdza, czy ma miejsce jakakolwiek aktualizacja. Jeśli nie, po prostu przerwiemy pętlę. Nasz pseudo-kod będzie:

Procedure Bellman-Ford(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
Return d

Aby śledzić cykl ujemny, możemy zmodyfikować nasz kod za pomocą procedury opisanej tutaj . Nasz wypełniony pseudo-kod będzie:

Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return d

Ścieżka drukowania:

Aby wydrukować najkrótszą ścieżkę do wierzchołka, będziemy iterować z powrotem do jego rodzica, aż znajdziemy NULL, a następnie wydrukujemy wierzchołki. Pseudo-kod będzie:

Procedure PathPrinting(u)
v := parent[u]
if v == NULL
    return
PathPrinting(v)
print -> u

Złożoność:

Ponieważ musimy rozluźnić maksymalnie krawędzie (V-1) razy, złożoność czasowa tego algorytmu będzie równa O (V * E), gdzie E oznacza liczbę krawędzi, jeśli użyjemy adjacency list do przedstawienia wykresu. Jeśli jednak do reprezentowania wykresu zostanie użyta adjacency matrix , złożoność czasowa wyniesie O (V ^ 3) . Powodem jest to, że możemy iterować wszystkie zbocza w czasie O (E), gdy używana jest adjacency list , ale zajmuje to czas O (V ^ 2), gdy używana jest adjacency matrix .

Dlaczego musimy rozluźnić wszystkie krawędzie co najwyżej (V-1) razy

Aby zrozumieć ten przykład, zaleca się krótkie zapoznanie się z algorytmem najkrótszej ścieżki Bellmana-Forda, który można znaleźć tutaj

W algorytmie Bellmana-Forda, aby znaleźć najkrótszą ścieżkę, musimy rozluźnić wszystkie krawędzie wykresu. Proces ten powtarza się co najwyżej (V-1) razy, gdzie V jest liczbą wierzchołków na wykresie.

Liczba iteracji potrzebnych do znalezienia najkrótszej ścieżki od źródła do wszystkich innych wierzchołków zależy od kolejności, w której wybraliśmy rozluźnienie krawędzi.

Spójrzmy na przykład:

Tutaj wierzchołek źródłowy wynosi 1. Dowiemy się jak najkrótszej odległości między źródłem a wszystkimi pozostałymi wierzchołkami. Widzimy wyraźnie, że aby dotrzeć do wierzchołka 4 , w najgorszym przypadku, przejdzie on przez krawędzie (V-1) . Teraz, w zależności od kolejności odkrywania krawędzi, odkrycie wierzchołka 4 może potrwać (V-1) razy. Nie rozumiesz? Użyjmy algorytmu Bellmana-Forda, aby znaleźć najkrótszą ścieżkę tutaj:

Użyjemy tej sekwencji:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  3->4  |  2->3  |  1->2  |
+--------+--------+--------+--------+

Do naszej pierwszej iteracji:

1. d [3] + koszt [3] [4] = nieskończoność . Nic to nie zmieni.
2. d [2] + koszt [2] [3] = nieskończoność . Nic to nie zmieni.
3. d [1] + koszt [1] [2] = 2 < d [2] . d [2] = 2 . rodzic [2] = 1 .

Widzimy, że nasz proces relaksacji zmienił tylko d [2] . Nasz wykres będzie wyglądał następująco:

Druga iteracja:

1. d [3] + koszt [3] [4] = nieskończoność . Nic to nie zmieni.
2. d [2] + koszt [2] [3] = 5 < d [3] . d [3] = 5 . rodzic [3] = 2.
3. To się nie zmieni.

Tym razem proces relaksacji zmienił d [3] . Nasz wykres będzie wyglądał następująco:

Trzecia iteracja:

1. d [3] + koszt [3] [4] = 7 < d [4] . d [4] = 7 . rodzic [4] = 3 .
2. To się nie zmieni.
3. To się nie zmieni.

Nasza trzecia iteracja w końcu znalazła najkrótszą drogę do 4 z 1 . Nasz wykres będzie wyglądał następująco:

Tak więc zajęło 3 iteracje, aby znaleźć najkrótszą ścieżkę. Po tym, bez względu na to, ile razy rozluźnimy krawędzie, wartości w d [] pozostaną takie same. Teraz, jeśli rozważymy inną sekwencję:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  1->2  |  2->3  |  3->4  |
+--------+--------+--------+--------+

Dostalibyśmy:

1. d [1] + koszt [1] [2] = 2 < d [2] . d [2] = 2 .
2. d [2] + koszt [2] [3] = 5 < d [3] . d [3] = 5 .
3. d [3] + koszt [3] [4] = 7 < d [4] . d [4] = 5 .

Nasza pierwsza iteracja znalazła najkrótszą ścieżkę od źródła do wszystkich innych węzłów. Możliwa jest inna sekwencja 1-> 2 , 3-> 4 , 2-> 3 , która da nam najkrótszą ścieżkę po 2 iteracjach. Możemy podjąć decyzję, że bez względu na to, jak ułożymy sekwencję, znalezienie najkrótszej ścieżki od źródła w tym przykładzie nie zajmie więcej niż 3 iteracje.

Możemy wnioskować, że w najlepszym przypadku potrzeba 1 iteracji, aby znaleźć najkrótszą ścieżkę od źródła . W najgorszym przypadku zajmie to iteracje (V-1) , dlatego powtarzamy proces relaksacji (V-1) razy.

Wykrywanie cyklu ujemnego na wykresie

Aby zrozumieć ten przykład, zaleca się krótkie zapoznanie się z algorytmem Bellmana-Forda, który można znaleźć tutaj

Za pomocą algorytmu Bellmana-Forda możemy wykryć, czy na naszym wykresie występuje cykl ujemny. Wiemy, że aby znaleźć najkrótszą ścieżkę, musimy rozluźnić wszystkie krawędzie wykresu (V-1) razy, gdzie V jest liczbą wierzchołków na wykresie. Widzieliśmy już, że w tym przykładzie po iteracjach (V-1) nie możemy zaktualizować d [] , bez względu na to, ile wykonamy iteracji. Czy możemy?

Jeśli na wykresie występuje cykl ujemny, nawet po iteracjach (V-1) , możemy zaktualizować d [] . Dzieje się tak, ponieważ dla każdej iteracji przejście przez cykl ujemny zawsze zmniejsza koszt najkrótszej ścieżki. Dlatego algorytm Bellmana-Forda ogranicza liczbę iteracji do (V-1) . Gdybyśmy użyli tutaj algorytmu Dijkstry, utknęlibyśmy w nieskończonej pętli. Skoncentrujmy się jednak na znalezieniu cyklu ujemnego.

Załóżmy, że mamy wykres:

Wybierzmy wierzchołek 1 jako źródło . Po zastosowaniu algorytmu najkrótszej ścieżki Bellmana-Forda do wykresu, dowiemy się o odległości od źródła do wszystkich pozostałych wierzchołków.

Tak wygląda wykres po (V-1) = 3 iteracjach. Powinien to być wynik, ponieważ istnieją 4 krawędzie, potrzebujemy co najwyżej 3 iteracji, aby znaleźć najkrótszą ścieżkę. Więc albo to jest odpowiedź, albo na wykresie występuje cykl ujemnej wagi. Aby to stwierdzić, po iteracjach (V-1) wykonujemy jeszcze jedną iterację końcową, a jeśli odległość nadal maleje, oznacza to, że na wykresie zdecydowanie występuje ujemny cykl wagowy.

Na przykład: jeśli sprawdzimy 2-3 , d [2] + koszt [2] [3] da nam 1, który jest mniejszy niż d [3] . Możemy zatem stwierdzić, że na naszym wykresie występuje cykl ujemny.

Jak więc odkryć cykl ujemny? Wprowadzamy trochę modyfikacji do procedury Bellmana-Forda:

Procedure NegativeCycleDetector(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return "No Negative Cycle"

W ten sposób dowiadujemy się, czy na wykresie występuje cykl ujemny. Możemy również zmodyfikować algorytm Bellmana-Forda, aby śledzić cykle ujemne.