algorithm
Bellman-Ford-Algorithmus

Bemerkungen

Single Source Shortest Path Algorithm (In einem Graphen gibt es einen negativen Zyklus)

Bevor Sie dieses Beispiel lesen, ist eine kurze Vorstellung von der Kantenentspannung erforderlich. Sie können es von hier lernen

Der Bellman-Ford- Algorithmus berechnet die kürzesten Pfade von einem einzelnen Quellscheitelpunkt zu allen anderen Scheitelpunkten in einem gewichteten Digraphen. Obwohl es langsamer als der Algorithmus von Dijkstra ist , funktioniert es in den Fällen, in denen das Gewicht der Kante negativ ist, und es findet auch ein negatives Gewicht im Diagramm. Das Problem mit dem Algorithmus von Dijkstra besteht darin, dass Sie bei einem negativen Zyklus den Zyklus immer wieder durchlaufen und den Abstand zwischen zwei Scheitelpunkten verringern.

Die Idee dieses Algorithmus besteht darin, alle Kanten dieses Graphen in zufälliger Reihenfolge nacheinander zu durchlaufen. Es kann eine beliebige Reihenfolge sein. Sie müssen jedoch sicherstellen, dass, wenn uv (wobei u und v zwei Scheitelpunkte in einem Diagramm sind) eine Ihrer Ordnungen ist, eine Kante von u nach v vorhanden sein muss . Normalerweise wird es direkt aus der Reihenfolge der Eingabe übernommen. Wieder funktioniert jede zufällige Reihenfolge.

Nach der Auswahl der Reihenfolge werden wir die Kanten gemäß der Entspannungsformel entspannen . Für eine gegebene Kante uv , die von u nach v geht, lautet die Relaxationsformel:

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

Das heißt, wenn der Abstand von der Quelle zu einem Scheitelpunkt u + die Gewichtung der Kante uv geringer ist als der Abstand von der Quelle zu einem anderen Scheitelpunkt v , aktualisieren wir den Abstand von der Quelle nach v . Wir müssen die Kanten meistens (V-1) entspannen, wobei V die Anzahl der Kanten in der Grafik ist. Warum (V-1) fragst du? Wir werden es in einem anderen Beispiel erklären. Wir werden auch den Elternscheitelpunkt eines Scheitelpunkts verfolgen, dh wenn wir eine Kante entspannen, setzen wir:

parent[v] = u

Dies bedeutet, dass wir einen weiteren kürzeren Weg gefunden haben, um v über u zu erreichen. Wir werden dies später benötigen, um den kürzesten Weg von der Quelle zum gewünschten Scheitelpunkt zu drucken.

Schauen wir uns ein Beispiel an. Wir haben eine Grafik:

Wir haben 1 als Quellscheitelpunkt ausgewählt. Wir möchten den kürzesten Weg von der Quelle zu allen anderen Scheitelpunkten herausfinden.

Zuerst ist d [1] = 0, weil es die Quelle ist. Und Ruhe ist unendlich , weil wir ihre Entfernung noch nicht kennen.

Wir werden die Kanten in dieser Reihenfolge entspannen:

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

Sie können eine beliebige Sequenz nehmen. Wenn wir einmal die Kanten entspannen , was bekommen wir dann? Wir erhalten den Abstand von der Quelle zu allen anderen Knoten des Pfades, der höchstens eine Kante verwendet. Lassen Sie uns nun die Kanten entspannen und die Werte von d [] aktualisieren. Wir bekommen:

1. d [4] + cost [4] [5] = unendlich + 7 = unendlich . Wir können diesen nicht aktualisieren.
2. d [2] + cost [3] [4] = unendlich . Wir können diesen nicht aktualisieren.
3. d [1] + cost [1] [2] = 0 + 2 = 2 < d [2] . Also ist d [2] = 2 . Auch Elternteil [2] = 1 .
4. d [1] + Kosten [1] [4] = 4 . Also ist d [4] = 4 < d [4] . Elternteil [4] = 1 .
5. d [4] + Kosten [4] [6] = 9 . d [6] = 9 < d [6] . Elternteil [6] = 4 .
6. d [2] + Kosten [2] [2] = unendlich . Wir können diesen nicht aktualisieren.

Wir konnten einige Scheitelpunkte nicht aktualisieren, da die Bedingung d[u] + cost[u][v] < d[v] nicht übereinstimmte. Wie bereits erwähnt, haben wir die Pfade von der Quelle zu anderen Knoten mit maximal 1 Kante gefunden.

Bei der zweiten Iteration erhalten Sie den Pfad mit zwei Knoten. Wir bekommen:

1. d [4] + Kosten [4] [5] = 12 < d [5] . d [5] = 12 . Elternteil [5] = 4 .
2. d [3] + Kosten [3] [4] = 1 < d [4] . d [4] = 1 . Elternteil [4] = 3 .
3. d [3] bleibt unverändert.
4. d [4] bleibt unverändert.
5. d [4] + Kosten [4] [6] = 6 < d [6] . d [6] = 6 . Elternteil [6] = 4 .
6. d [3] bleibt unverändert.

Unser Diagramm wird wie folgt aussehen:

Unsere dritte Iteration wird nur den Knoten 5 aktualisieren, wobei d [5] 8 ist . Unser Diagramm wird wie folgt aussehen:

Unabhängig davon, wie viele Wiederholungen wir durchführen, haben wir dieselben Abstände. Wir werden also ein Flag behalten, das prüft, ob eine Aktualisierung stattfindet oder nicht. Wenn nicht, brechen wir einfach die Schleife. Unser Pseudo-Code lautet:

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

Um den negativen Zyklus nachverfolgen zu können, können wir unseren Code mithilfe des hier beschriebenen Verfahrens ändern. Unser vollständiger Pseudo-Code lautet:

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

Druckpfad:

Um den kürzesten Pfad zu einem Scheitelpunkt zu drucken, werden wir zu seinem übergeordneten Element zurückkehren, bis wir NULL finden und dann die Scheitelpunkte drucken. Der Pseudo-Code lautet:

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

Komplexität:

Da wir die Kanten maximal (V-1) entspannen müssen, ist die zeitliche Komplexität dieses Algorithmus gleich O (V * E), wobei E die Anzahl der Kanten angibt, wenn wir die Grafik mit einer adjacency list darstellen. Wenn jedoch eine adjacency matrix zur Darstellung des Graphen verwendet wird, ist die Zeitkomplexität O (V ^ 3) . Grund ist, dass wir in O (E) -Zeit alle Kanten durchlaufen können, wenn die adjacency list verwendet wird, aber es dauert O (V ^ 2), wenn die adjacency matrix verwendet wird.

Warum müssen wir alle Kanten (V-1) meistens entspannen?

Um dieses Beispiel zu verstehen, wird empfohlen, einen kurzen Überblick über den Bellman-Ford-Algorithmus für den kürzesten Weg zu haben, der hier zu finden ist

Um den kürzesten Weg herauszufinden, müssen wir beim Bellman-Ford-Algorithmus alle Kanten des Diagramms entspannen . Dieser Vorgang wird höchstens (V-1) wiederholt, wobei V die Anzahl der Scheitelpunkte in der Grafik ist.

Die Anzahl der Iterationen, die erforderlich sind, um den kürzesten Pfad von der Quelle zu allen anderen Scheitelpunkten herauszufinden, hängt von der Reihenfolge ab, die wir zum Entspannen der Kanten auswählen.

Schauen wir uns ein Beispiel an:

Hier ist der Quellscheitelpunkt 1. Wir ermitteln den kürzesten Abstand zwischen der Quelle und allen anderen Scheitelpunkten. Wir können deutlich erkennen, dass im letzten Fall (V-1) Kanten benötigt werden, um den Scheitelpunkt 4 zu erreichen. Abhängig von der Reihenfolge, in der die Kanten erkannt werden, dauert es möglicherweise (V-1) , bis der Scheitelpunkt 4 erkannt wird . Habe es nicht verstanden Verwenden Sie den Bellman-Ford-Algorithmus, um den kürzesten Weg hier herauszufinden:

Wir werden diese Sequenz verwenden:

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

Für unsere erste Wiederholung:

1. d [3] + Kosten [3] [4] = unendlich . Es wird sich nichts ändern.
2. d [2] + Kosten [2] [3] = unendlich . Es wird sich nichts ändern.
3. d [1] + Kosten [1] [2] = 2 < d [2] . d [2] = 2 . Elternteil [2] = 1 .

Wir können sehen, dass sich unser Entspannungsprozess nur durch d [2] verändert hat . Unser Diagramm wird wie folgt aussehen:

Zweite Iteration:

1. d [3] + Kosten [3] [4] = unendlich . Es wird sich nichts ändern.
2. d [2] + Kosten [2] [3] = 5 < d [3] . d [3] = 5 . Elternteil [3] = 2.
3. Es wird nicht geändert.

Diesmal änderte sich der Relaxationsprozess d [3] . Unser Diagramm wird wie folgt aussehen:

Dritte Iteration:

1. d [3] + Kosten [3] [4] = 7 < d [4] . d [4] = 7 . Elternteil [4] = 3 .
2. Es wird nicht geändert.
3. Es wird nicht geändert.

Unsere dritte Iteration fand schließlich den kürzesten Weg von 1 zu 4 . Unser Diagramm wird wie folgt aussehen:

Es dauerte also 3 Iterationen, um den kürzesten Weg herauszufinden. Unabhängig davon, wie oft wir die Kanten entspannen , bleiben die Werte in d [] gleich. Nun, wenn wir eine andere Sequenz betrachtet haben:

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

Wir würden bekommen:

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

Unsere erste Iteration hat den kürzesten Weg von der Quelle zu allen anderen Knoten gefunden. Eine andere Sequenz 1-> 2 , 3-> 4 , 2-> 3 ist möglich, die nach 2 Iterationen den kürzesten Weg ergibt. Wir können zu der Entscheidung kommen, dass unabhängig von der Anordnung der Sequenz nicht mehr als 3 Iterationen erforderlich sind, um den kürzesten Pfad in diesem Beispiel aus der Quelle herauszufinden.

Wir können feststellen , dass für den besten Fall ist es 1 Iteration nehme den kürzesten Weg von der Quelle zu erfahren. Im schlimmsten Fall werden (V-1) -Iterationen benötigt, weshalb wir den Vorgang der Relaxation (V-1) wiederholen.

Negativen Zyklus in einem Diagramm erkennen

Um dieses Beispiel zu verstehen, wird empfohlen, eine kurze Vorstellung über den Bellman-Ford-Algorithmus zu haben, die hier zu finden ist

Mit dem Bellman-Ford-Algorithmus können wir feststellen, ob in unserer Grafik ein negativer Zyklus vorliegt. Um den kürzesten Weg herauszufinden, müssen wir alle Kanten des Graphen (V-1) mal entspannen , wobei V die Anzahl der Scheitelpunkte in einem Graphen ist. Wir haben bereits gesehen, dass wir in diesem Beispiel nach (V-1) Iterationen d [] nicht aktualisieren können, unabhängig davon, wie viele Iterationen wir durchführen. Oder können wir

Wenn in einem Graphen ein negativer Zyklus vorhanden ist, können Sie auch nach (V-1) Iterationen d [] aktualisieren. Dies geschieht, weil das Durchlaufen des negativen Zyklus bei jeder Wiederholung immer die Kosten des kürzesten Pfades senkt. Daher begrenzt der Bellman-Ford-Algorithmus die Anzahl der Iterationen auf (V-1) . Wenn wir den Algorithmus von Dijkstra hier verwenden, stecken wir in einer Endlosschleife. Konzentrieren wir uns jedoch darauf, den negativen Zyklus zu finden.

Nehmen wir an, wir haben eine Grafik:

Wir wählen den Scheitelpunkt 1 als Quelle . Nachdem wir den Algorithmus für den kürzesten Weg von Bellman-Ford auf den Graphen angewendet haben, ermitteln wir die Abstände von der Quelle zu allen anderen Scheitelpunkten.

So sieht der Graph nach (V-1) = 3 Iterationen aus. Es sollte das Ergebnis sein, da es 4 Kanten gibt, wir benötigen höchstens 3 Iterationen, um den kürzesten Weg herauszufinden. Entweder ist dies die Antwort oder es gibt einen negativen Gewichtszyklus in der Grafik. Um zu finden, dass wir nach (V-1) -Iterationen noch eine letzte Iteration durchführen, und wenn der Abstand weiter abnimmt, bedeutet dies, dass es definitiv einen negativen Gewichtszyklus in der Grafik gibt.

Für dieses Beispiel: Wenn wir 2-3 überprüfen, ergibt d [2] + cost [2] [3] 1, was weniger als d [3] ist . Daraus können wir schließen, dass unsere Grafik einen negativen Zyklus aufweist.

Wie finden wir den negativen Zyklus heraus? Wir ändern das Bellman-Ford-Verfahren ein wenig:

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"

So finden wir heraus, ob in einem Graphen ein negativer Zyklus vorliegt. Wir können den Bellman-Ford-Algorithmus auch modifizieren, um negative Zyklen zu verfolgen.