Het Bellman Ford-algoritme helpt ons het kortste pad te vinden van een hoekpunt naar alle andere hoekpunten van een gewogen grafiek.
Het is vergelijkbaar met Dijkstra's algoritme, maar het kan werken met grafieken waarin randen een negatief gewicht kunnen hebben.
Waarom zou iemand in het echte leven ooit randen hebben met negatieve gewichten?
Negatieve gewichtsranden lijken in eerste instantie misschien nutteloos, maar ze kunnen veel verschijnselen verklaren, zoals cashflow, de warmte die vrijkomt / geabsorbeerd wordt bij een chemische reactie, enz.
Als er bijvoorbeeld verschillende manieren zijn om van de ene chemische stof A naar de andere chemische stof B te komen, zal elke methode subreacties hebben die zowel warmteafvoer als absorptie omvatten.
Als we de reeks reacties willen vinden waarbij minimale energie vereist is, dan moeten we de warmteabsorptie als negatieve gewichten en warmteafvoer als positieve gewichten kunnen beschouwen.
Waarom moeten we voorzichtig zijn met negatieve gewichten?
Negatieve gewichtsranden kunnen negatieve gewichtscycli creëren, dwz een cyclus die de totale padafstand verkleint door terug te keren naar hetzelfde punt.
Cycli met een negatief gewicht kunnen een onjuist resultaat geven bij het zoeken naar de kortste weg
Kortste-padalgoritmen zoals Dijkstra's algoritme die een dergelijke cyclus niet kunnen detecteren, kunnen een onjuist resultaat geven omdat ze een negatieve weegcyclus kunnen doorlopen en de padlengte kunnen verkleinen.
Hoe het algoritme van Bellman Ford werkt
Het Bellman Ford-algoritme werkt door de lengte van het pad van het beginpunt tot alle andere hoekpunten te overschatten. Vervolgens versoepelt het die schattingen iteratief door nieuwe paden te vinden die korter zijn dan de eerder overschatte paden.
Door dit herhaaldelijk te doen voor alle vertices, kunnen we garanderen dat het resultaat wordt geoptimaliseerd.
Stap-1 voor het algoritme van Bellman Ford 
Stap-2 voor het algoritme van Bellman Ford 
Stap-3 voor het algoritme van Bellman Ford 
Stap-4 voor het algoritme van Bellman Ford 
Stap-5 voor het algoritme van Bellman Ford 
Stap-6 voor het algoritme van Bellman Ford
Bellman Ford Pseudocode
We moeten de padafstand van elk hoekpunt behouden. We kunnen dat opslaan in een array van grootte v, waarbij v het aantal hoekpunten is.
We willen ook het kortste pad kunnen krijgen, niet alleen de lengte van het kortste pad weten. Hiervoor brengen we elk hoekpunt in kaart met het hoekpunt waarvan de padlengte het laatst is bijgewerkt.
Zodra het algoritme voorbij is, kunnen we teruggaan van het doelpunt naar het bronpunt om het pad te vinden.
functie bellmanFord (G, S) voor elk hoekpunt V in G afstand (V) <- oneindig vorige (V) <- NULL afstand (S) <- 0 voor elk hoekpunt V in G voor elke rand (U, V) in G tempDistance <- afstand (U) + edge_weight (U, V) als tempDistance <afstand (V) afstand (V) <- tempDistance vorige (V) <- U voor elke rand (U, V) in G If afstand (U) + edge_weight (U, V) <afstand (V) Fout: negatieve cyclus bestaat retourafstand (), vorige ()
Bellman Ford tegen Dijkstra
Het algoritme van Bellman Ford en het algoritme van Dijkstra lijken qua structuur sterk op elkaar. Terwijl Dijkstra alleen naar de directe buren van een hoekpunt kijkt, doorloopt Bellman elke rand in elke iteratie.
Dijkstra's vs Bellman Ford's algoritme
Python, Java en C / C ++ voorbeelden
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; )
Bellman Ford's complexiteit
Tijdscomplexiteit
| Complexiteit in het beste geval | O (E) |
| Gemiddelde casuscomplexiteit | O (VE) |
| Complexiteit in het ergste geval | O (VE) |
Complexiteit van de ruimte
En de complexiteit van de ruimte is O(V).
Algoritme-toepassingen van Bellman Ford
- Voor het berekenen van de kortste paden in routeringsalgoritmen
- Om de kortste weg te vinden
