Bellman Fords Algorithmus

Der Bellman Ford-Algorithmus hilft uns, den kürzesten Weg von einem Scheitelpunkt zu allen anderen Scheitelpunkten eines gewichteten Graphen zu finden.

Es ähnelt dem Dijkstra-Algorithmus, kann jedoch mit Diagrammen arbeiten, in denen Kanten negative Gewichte haben können.

Warum sollte man im wirklichen Leben jemals Kanten mit negativen Gewichten haben?

Negative Gewichtskanten mögen zunächst nutzlos erscheinen, aber sie können viele Phänomene wie den Cashflow, die bei einer chemischen Reaktion freigesetzte / absorbierte Wärme usw. erklären.

Wenn es beispielsweise unterschiedliche Wege gibt, von einer Chemikalie A zu einer anderen Chemikalie B zu gelangen, weist jede Methode Unterreaktionen auf, die sowohl Wärmeableitung als auch Absorption umfassen.

Wenn wir die Reaktionen finden wollen, bei denen minimale Energie benötigt wird, müssen wir in der Lage sein, die Wärmeabsorption als negative Gewichte und die Wärmeableitung als positive Gewichte zu berücksichtigen.

Warum müssen wir mit negativen Gewichten vorsichtig sein?

Negative Gewichtskanten können negative Gewichtszyklen erzeugen, dh einen Zyklus, der die Gesamtwegentfernung verringert, indem er zum selben Punkt zurückkehrt.

Negative Gewichtszyklen können zu einem falschen Ergebnis führen, wenn versucht wird, den kürzesten Weg zu finden

Algorithmen mit kürzesten Pfaden wie der Dijkstra-Algorithmus, die einen solchen Zyklus nicht erkennen können, können zu einem falschen Ergebnis führen, da sie einen negativen Gewichtszyklus durchlaufen und die Pfadlänge verringern können.

Wie der Algorithmus von Bellman Ford funktioniert

Der Bellman Ford-Algorithmus überschätzt die Länge des Pfades vom Startscheitelpunkt zu allen anderen Scheitelpunkten. Anschließend werden diese Schätzungen iterativ gelockert, indem neue Pfade gefunden werden, die kürzer als die zuvor überschätzten Pfade sind.

Indem wir dies wiederholt für alle Scheitelpunkte tun, können wir sicherstellen, dass das Ergebnis optimiert wird.

Schritt 1 für den Algorithmus von Bellman Ford

Schritt 2 für den Algorithmus von Bellman Ford

Schritt 3 für den Algorithmus von Bellman Ford

Schritt 4 für den Algorithmus von Bellman Ford

Schritt 5 für den Algorithmus von Bellman Ford

Schritt 6 für den Algorithmus von Bellman Ford

Bellman Ford Pseudocode

Wir müssen den Pfadabstand jedes Scheitelpunkts einhalten. Wir können das in einem Array der Größe v speichern, wobei v die Anzahl der Eckpunkte ist.

Wir wollen auch den kürzesten Weg finden können, nicht nur die Länge des kürzesten Weges kennen. Dazu ordnen wir jeden Scheitelpunkt dem Scheitelpunkt zu, der zuletzt seine Pfadlänge aktualisiert hat.

Sobald der Algorithmus beendet ist, können wir vom Zielscheitelpunkt zum Quellscheitelpunkt zurückkehren, um den Pfad zu finden.

 Funktion bellmanFord (G, S) für jeden Scheitelpunkt V in G Abstand (V) <- unendlich vorheriger (V) <- NULL Abstand (S) <- 0 für jeden Scheitelpunkt V in G für jede Kante (U, V) in G. tempDistance <- Abstand (U) + Kantengewicht (U, V) wenn tempDistance <Abstand (V) Abstand (V) <- tempDistance vorher (V) <- U für jede Kante (U, V) in G Wenn Abstand (U) + edge_weight (U, V) <distance (V) Fehler: Negativer Zyklus Gibt Rückgabedistanz (), vorherige ()

Bellman Ford gegen Dijkstra

Der Bellman Ford-Algorithmus und der Dijkstra-Algorithmus sind in ihrer Struktur sehr ähnlich. Während Dijkstra nur auf die unmittelbaren Nachbarn eines Scheitelpunkts schaut, geht Bellman in jeder Iteration jede Kante durch.

Dijkstra's gegen Bellman Ford's Algorithmus

Beispiele für Python, Java und C / C ++

Python Java C C ++

 # Bellman Ford Algorithm in Python class Graph: def __init__(self, vertices): self.V = vertices # Total number of vertices in the graph self.graph = () # Array of edges # Add edges def add_edge(self, s, d, w): self.graph.append((s, d, w)) # Print the solution def print_solution(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("(0) (1)".format(i, dist(i))) def bellman_ford(self, src): # Step 1: fill the distance array and predecessor array dist = (float("Inf")) * self.V # Mark the source vertex dist(src) = 0 # Step 2: relax edges |V| - 1 times for _ in range(self.V - 1): for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): dist(d) = dist(s) + w # Step 3: detect negative cycle # if value changes then we have a negative cycle in the graph # and we cannot find the shortest distances for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): print("Graph contains negative weight cycle") return # No negative weight cycle found! # Print the distance and predecessor array self.print_solution(dist) g = Graph(5) g.add_edge(0, 1, 5) g.add_edge(0, 2, 4) g.add_edge(1, 3, 3) g.add_edge(2, 1, 6) g.add_edge(3, 2, 2) g.bellman_ford(0)

 // Bellman Ford Algorithm in Java class CreateGraph ( // CreateGraph - it consists of edges class CreateEdge ( int s, d, w; CreateEdge() ( s = d = w = 0; ) ); int V, E; CreateEdge edge(); // Creates a graph with V vertices and E edges CreateGraph(int v, int e) ( V = v; E = e; edge = new CreateEdge(e); for (int i = 0; i < e; ++i) edge(i) = new CreateEdge(); ) void BellmanFord(CreateGraph graph, int s) ( int V = graph.V, E = graph.E; int dist() = new int(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; ++i) dist(i) = Integer.MAX_VALUE; // Mark the source vertex dist(s) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i < V; ++i) ( for (int j = 0; j < E; ++j) ( // Get the edge data int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int j = 0; j < E; ++j) ( int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) ( System.out.println("CreateGraph contains negative w cycle"); return; ) ) // No negative w cycle found! // Print the distance and predecessor array printSolution(dist, V); ) // Print the solution void printSolution(int dist(), int V) ( System.out.println("Vertex Distance from Source"); for (int i = 0; i 1 graph.edge(0).s = 0; graph.edge(0).d = 1; graph.edge(0).w = 5; // edge 0 --> 2 graph.edge(1).s = 0; graph.edge(1).d = 2; graph.edge(1).w = 4; // edge 1 --> 3 graph.edge(2).s = 1; graph.edge(2).d = 3; graph.edge(2).w = 3; // edge 2 --> 1 graph.edge(3).s = 2; graph.edge(3).d = 1; graph.edge(3).w = 6; // edge 3 --> 2 graph.edge(4).s = 3; graph.edge(4).d = 2; graph.edge(4).w = 2; graph.BellmanFord(graph, 0); // 0 is the source vertex ) )

 // Bellman Ford Algorithm in C #include #include #define INFINITY 99999 //struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //weight of the edge (u,v) ); //Graph - it consists of edges struct Graph ( int V; //total number of vertices in the graph int E; //total number of edges in the graph struct Edge *edge; //array of edges ); void bellmanford(struct Graph *g, int source); void display(int arr(), int size); int main(void) ( //create graph struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph)); g->V = 4; //total vertices g->E = 5; //total edges //array of edges for graph g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge)); //------- adding the edges of the graph /* edge(u, v) where u = start vertex of the edge (u,v) v = end vertex of the edge (u,v) w is the weight of the edge (u,v) */ //edge 0 --> 1 g->edge(0).u = 0; g->edge(0).v = 1; g->edge(0).w = 5; //edge 0 --> 2 g->edge(1).u = 0; g->edge(1).v = 2; g->edge(1).w = 4; //edge 1 --> 3 g->edge(2).u = 1; g->edge(2).v = 3; g->edge(2).w = 3; //edge 2 --> 1 g->edge(3).u = 2; g->edge(3).v = 1; g->edge(3).w = 6; //edge 3 --> 2 g->edge(4).u = 3; g->edge(4).v = 2; g->edge(4).w = 2; bellmanford(g, 0); //0 is the source vertex return 0; ) void bellmanford(struct Graph *g, int source) ( //variables int i, j, u, v, w; //total vertex in the graph g int tV = g->V; //total edge in the graph g int tE = g->E; //distance array //size equal to the number of vertices of the graph g int d(tV); //predecessor array //size equal to the number of vertices of the graph g int p(tV); //step 1: fill the distance array and predecessor array for (i = 0; i < tV; i++) ( d(i) = INFINITY; p(i) = 0; ) //mark the source vertex d(source) = 0; //step 2: relax edges |V| - 1 times for (i = 1; i <= tV - 1; i++) ( for (j = 0; j edge(j).u; v = g->edge(j).v; w = g->edge(j).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( d(v) = d(u) + w; p(v) = u; ) ) ) //step 3: detect negative cycle //if value changes then we have a negative cycle in the graph //and we cannot find the shortest distances for (i = 0; i edge(i).u; v = g->edge(i).v; w = g->edge(i).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( printf("Negative weight cycle detected!"); return; ) ) //No negative weight cycle found! //print the distance and predecessor array printf("Distance array: "); display(d, tV); printf("Predecessor array: "); display(p, tV); ) void display(int arr(), int size) ( int i; for (i = 0; i < size; i++) ( printf("%d ", arr(i)); ) printf(""); )

 // Bellman Ford Algorithm in C++ #include // Struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //w of the edge (u,v) ); // Graph - it consists of edges struct Graph ( int V; // Total number of vertices in the graph int E; // Total number of edges in the graph struct Edge* edge; // Array of edges ); // Creates a graph with V vertices and E edges struct Graph* createGraph(int V, int E) ( struct Graph* graph = new Graph; graph->V = V; // Total Vertices graph->E = E; // Total edges // Array of edges for graph graph->edge = new Edge(E); return graph; ) // Printing the solution void printArr(int arr(), int size) ( int i; for (i = 0; i V; int E = graph->E; int dist(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; i++) dist(i) = INT_MAX; // Mark the source vertex dist(u) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i <= V - 1; i++) ( for (int j = 0; j edge(j).u; int v = graph->edge(j).v; int w = graph->edge(j).w; if (dist(u) != INT_MAX && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int i = 0; i edge(i).u; int v = graph->edge(i).v; int w = graph->edge(i).w; if (dist(u) != INT_MAX && dist(u) + w 1 graph->edge(0).u = 0; graph->edge(0).v = 1; graph->edge(0).w = 5; //edge 0 --> 2 graph->edge(1).u = 0; graph->edge(1).v = 2; graph->edge(1).w = 4; //edge 1 --> 3 graph->edge(2).u = 1; graph->edge(2).v = 3; graph->edge(2).w = 3; //edge 2 --> 1 graph->edge(3).u = 2; graph->edge(3).v = 1; graph->edge(3).w = 6; //edge 3 --> 2 graph->edge(4).u = 3; graph->edge(4).v = 2; graph->edge(4).w = 2; BellmanFord(graph, 0); //0 is the source vertex return 0; )