Bellman-Ford-Algorithmus

Im Vorgriff auf den Beginn des Kurses „Algorithmen für Entwickler“ haben sie eine weitere Übersetzung eines interessanten Artikels vorbereitet.

---

Problem : Wenn ein Graph und ein Anfangsscheitelpunkt src in einem Graphen gegeben sind, ist es notwendig, die kürzesten Wege von src zu allen Scheitelpunkten in einem gegebenen Graphen zu finden. Das Diagramm kann Kanten mit negativen Gewichten enthalten.

Wir haben bereits den Dijkstra-Algorithmus besprochen, um dieses Problem zu lösen. Der Dijkstra-Algorithmus ist ein gieriger Algorithmus, und seine Komplexität ist O (VLogV) (unter Verwendung des Fibonacci-Heap). Dijkstra funktioniert jedoch nicht für Diagramme mit negativer Kantengewichtung, während Bellman-Ford dies vollständig tut. Der Bellman-Ford-Algorithmus ist noch einfacher als der Dijkstra-Algorithmus und eignet sich gut für verteilte Systeme. Gleichzeitig ist seine Komplexität O (VE) , was mehr als der Indikator für den Dijkstra-Algorithmus ist.

Empfehlung : Bevor Sie mit der Anzeige der Lösung fortfahren, üben Sie sich selbst.

Algorithmus

Das Folgende sind detaillierte Schritte.

Eingabe : Graph und anfänglicher Vertex src .
Ausgabe : Die kürzeste Entfernung zu allen Scheitelpunkten von src. Wenn ein Zyklus mit negativem Gewicht auftritt, werden die kürzesten Abstände nicht berechnet, und es wird eine Meldung angezeigt, die das Vorhandensein eines solchen Zyklus anzeigt.

1. In diesem Schritt werden die Abstände vom Anfangsscheitelpunkt zu allen anderen Scheitelpunkten als unendlich initialisiert, und der Abstand zu src selbst wird mit 0 angenommen. Ein Array dist[] Größe |V| mit allen Werten gleich unendlich, mit Ausnahme des dist[src] -Elements, wobei src der ursprüngliche Scheitelpunkt ist.
2. Der zweite Schritt berechnet die kürzesten Entfernungen. Die folgenden Schritte müssen ausgeführt werden |V| -1 mal, wobei |V| - Die Anzahl der Eckpunkte in diesem Diagramm.
   
   • Führen Sie für jede UV- Kante die folgende Aktion aus:
     Wenn dist[v] > dist[u] + uv , dann aktualisiere dist[v]
dist [v] = dist [u] + uv
     
3. In diesem Schritt wird gemeldet, ob in der Grafik ein negativer Gewichtszyklus vorliegt. Führen Sie für jedes Kanten- UV Folgendes aus:
   
   
   • Wenn dist[v] > dist[u] + uv , enthält der Graph einen Zyklus mit negativem Gewicht.
     

Die Idee von Schritt 3 ist, dass Schritt 2 die kürzeste Distanz garantiert, wenn der Graph keinen Zyklus mit negativem Gewicht enthält. Wenn wir alle Kanten erneut durchgehen und einen kürzeren Pfad für einen der Scheitelpunkte erhalten, ist dies ein Signal für das Vorhandensein eines negativen Gewichtszyklus.

Wie funktioniert es Wie bei anderen dynamischen Programmieraufgaben berechnet der Algorithmus die kürzesten Pfade von unten nach oben. Zunächst werden die kürzesten Abstände berechnet, dh Pfade mit einer Länge von nicht mehr als einer Kante. Dann berechnet es die kürzesten Wege mit einer Länge von nicht mehr als zwei Kanten und so weiter. Nach der i-ten Iteration der äußeren Schleife werden die kürzesten Pfade mit einer Länge von nicht mehr als i Kanten berechnet. In jedem einfachen Pfad kann es maximal | V | -1 Kanten geben, so dass die äußere Schleife genau | V | -1 Mal läuft. Die Idee ist, dass, wenn wir den kürzesten Pfad mit nicht mehr als i Kanten berechnen, das Iterieren über alle Kanten garantiert, dass der kürzeste Pfad mit nicht mehr als i + 1 Kanten erhalten wird (der Beweis ist recht einfach, Sie können sich auf diese Vorlesung oder Videovorlesung vom MIT beziehen )

Beispiel

Schauen wir uns den Algorithmus im folgenden Diagrammbeispiel an. Bilder von hier aufgenommen .
Der anfängliche Scheitelpunkt sei 0. Nehmen Sie alle Entfernungen als unendlich, mit Ausnahme der Entfernung zu src selbst. Die Gesamtanzahl der Scheitelpunkte im Diagramm beträgt 5, sodass alle Kanten viermal verschoben werden müssen.



Lassen Sie die Rippen in der folgenden Reihenfolge herausarbeiten: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), ( E, D). Die folgenden Abstände erhalten wir, als der Durchgang entlang der Rippen zum ersten Mal abgeschlossen wurde. Die erste Zeile zeigt die Anfangsabstände, die zweite Zeile zeigt die Abstände, wenn die Kanten (B, E), (D, B), (B, D) und (A, B) verarbeitet werden. Die dritte Zeile zeigt den Bearbeitungsabstand (A, C). Die vierte Zeile zeigt, was passiert, wenn (D, C), (B, C) und (E, D) verarbeitet werden.



Die erste Iteration stellt sicher, dass alle kürzesten Pfade nicht länger als der Pfad einer Kante sind. Die folgenden Abstände erhalten wir, wenn der zweite Durchgang an allen Kanten abgeschlossen ist (die letzte Zeile zeigt die Endwerte).



Die zweite Iteration stellt sicher, dass alle kürzesten Pfade eine Länge von höchstens 2 Kanten haben. Der Algorithmus läuft 2 weitere Male entlang aller Kanten. Entfernungen werden nach der zweiten Iteration minimiert, sodass die dritten und vierten Iterationen die Entfernungswerte nicht aktualisieren.

Implementierung:

 # Python program for Bellman-Ford's single source # shortest path algorithm. from collections import defaultdict # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # default dictionary to store graph # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("% d \t\t % d" % (i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float("Inf")] * self.V dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. A simple shortest # path from src to any other vertex can have at-most |V| - 1 # edges for i in range(self.V - 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print "Graph contains negative weight cycle" return # print all distance self.printArr(dist) g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # Print the solution g.BellmanFord(0) # This code is contributed by Neelam Yadav 

Ausgabewerte:



Anmerkungen:

1. Negative Gewichte werden in verschiedenen Grafikanwendungen gefunden. Anstatt beispielsweise die Kosten eines Pfades zu erhöhen, können wir davon profitieren, wenn wir einem bestimmten Pfad folgen.
2. Der Bellman-Ford-Algorithmus funktioniert besser für verteilte Systeme (besser als der Dijkstra-Algorithmus). Im Gegensatz zu Dijkstra, wo wir den Mindestwert aller Eckpunkte ermitteln müssen, werden bei Bellman Ford Kanten einzeln betrachtet.

Übungen:

1. Der Bellman-Ford-Standardalgorithmus meldet nur dann kürzeste Wege, wenn er keine Zyklen mit negativem Gewicht aufweist. Ändern Sie es so, dass es die kürzesten Pfade meldet, auch wenn es einen solchen Zyklus gibt.
2. Können wir den Dijkstra-Algorithmus verwenden, um die kürzesten Pfade in einer Grafik mit negativen Gewichten zu finden? Es gibt eine solche Idee: Berechnen Sie den minimalen Gewichtswert, addieren Sie einen positiven Wert (der dem absoluten Wert des minimalen Gewichtswerts entspricht) zu allen Gewichten und führen Sie den Dijkstra-Algorithmus für das modifizierte Diagramm aus. Wird ein solcher Algorithmus funktionieren?

Einfache Implementierung des Bellman-Ford-Algorithmus

Quellen:

www.youtube.com/watch?v=Ttezuzs39nk
en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf