Algoritmus Bellman Forda nám pomáha nájsť najkratšiu cestu od vrcholu k všetkým ostatným vrcholom váženého grafu.
Je to podobné ako s Dijkstrovým algoritmom, ale dokáže pracovať s grafmi, v ktorých môžu mať hrany záporné váhy.
Prečo by niekto mal v reálnom čase hrany so zápornými váhami?
Hrany s negatívnou hmotnosťou sa spočiatku môžu javiť ako zbytočné, ale môžu vysvetliť množstvo javov, ako sú hotovostné toky, teplo uvoľňované / absorbované chemickou reakciou atď.
Napríklad, ak existujú rôzne spôsoby dosiahnutia z jednej chemikálie A na inú chemikáliu B, každá metóda bude mať subreakcie zahŕňajúce ako odvod tepla, tak aj absorpciu.
Ak chceme nájsť súbor reakcií, pri ktorých sa vyžaduje minimálna energia, potom budeme musieť byť schopní zohľadniť absorpciu tepla ako záporné hmotnosti a odvod tepla ako kladné váhy.
Prečo musíme byť opatrní pri negatívnych váhach?
Hrany zápornej hmotnosti môžu vytvárať cykly zápornej hmotnosti, tj cyklus, ktorý zníži celkovú vzdialenosť dráhy návratom do rovnakého bodu.
Negatívne váhové cykly môžu dať nesprávny výsledok pri pokuse o nájdenie najkratšej cesty
Najkratšie algoritmy cesty, ako je Dijkstraov algoritmus, ktoré nie sú schopné detekovať takýto cyklus, môžu poskytnúť nesprávny výsledok, pretože môžu prechádzať negatívnym váhovým cyklom a zmenšiť dĺžku cesty.
Ako funguje algoritmus spoločnosti Bellman Ford
Algoritmus Bellman Ford funguje tak, že nadhodnocuje dĺžku cesty od východiskového vrcholu k všetkým ostatným vrcholom. Potom tieto odhady iteratívne uvoľní nájdením nových ciest, ktoré sú kratšie ako predtým preceňované cesty.
Ak to urobíme opakovane pre všetky vrcholy, môžeme zaručiť, že výsledok bude optimalizovaný.
Krok 1 pre algoritmus Bellman Ford 
Krok 2 pre algoritmus Bellman Ford 
Krok 3 pre algoritmus Bellman Ford 
Krok 4 pre algoritmus Bellman Ford 
Krok 5 pre algoritmus Bellman Ford 
Krok 6 pre algoritmus Bellman Ford
Pseudokód Bellman Ford
Musíme zachovať dráhovú vzdialenosť každého vrcholu. Môžeme to uložiť do poľa veľkosti v, kde v je počet vrcholov.
Chceme tiež mať možnosť dostať sa na najkratšiu cestu, nielen poznať dĺžku najkratšej cesty. Za týmto účelom mapujeme každý vrchol na vrchol, ktorý naposledy aktualizoval svoju dĺžku cesty.
Po dokončení algoritmu môžeme nájsť cestu späť z cieľového vrcholu do zdrojového.
funkcia bellmanFord (G, S) pre každý vrchol V vo vzdialenosti G (V) <- nekonečná predchádzajúca (V) <- NULL vzdialenosť (S) <- 0 pre každý vrchol V v G pre každú hranu (U, V) v G tempDistance <- vzdialenosť (U) + hrana_hmotnosti (U, V), ak tempDistance <vzdialenosť (V) vzdialenosť (V) <- tempDistance predchádzajúca (V) <- U pre každú hranu (U, V) v G If vzdialenosť (U) + edge_weight (U, V) <distance (V) Error: Negative Cycle Exists return distance (), previous ()
Bellman Ford vs Dijkstra
Algoritmus Bellmana Forda a Dijkstraov algoritmus majú veľmi podobnú štruktúru. Zatiaľ čo Dijkstra pozerá iba na bezprostredných susedov vrcholu, Bellman prechádza každou hranou v každej iterácii.
Algoritmus Dijkstra vs Bellman Ford
Príklady jazyka Python, Java a 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; )
Zložitosť spoločnosti Bellman Ford
Časová zložitosť
| Najlepšia zložitosť prípadu | O (E) |
| Priemerná zložitosť prípadu | O (VE) |
| Najhoršia zložitosť prípadu | O (VE) |
Zložitosť vesmíru
A vesmírna zložitosť je O(V).
Aplikácie algoritmov spoločnosti Bellman Ford
- Na výpočet najkratších ciest v smerovacích algoritmoch
- Za nájdenie najkratšej cesty
