Bellmano Fordo algoritmas padeda mums rasti trumpiausią kelią nuo viršūnės iki visų kitų svertinio grafo viršūnių.
Tai panašu į Dijkstros algoritmą, tačiau jis gali dirbti su grafikais, kuriuose kraštai gali turėti neigiamą svorį.
Kodėl realiame gyvenime kada nors turėtų kraštai su neigiamu svoriu?
Neigiami svorio kraštai iš pradžių gali atrodyti nenaudingi, tačiau jie gali paaiškinti daugybę reiškinių, tokių kaip pinigų srautas, šiluma, išsiskirianti / absorbuota cheminės reakcijos metu ir kt.
Pavyzdžiui, jei yra skirtingi būdai pasiekti vieną cheminę medžiagą A kitai cheminei medžiagai B, kiekvienam metodui būdingos subreakcijos, apimančios šilumos išsklaidymą ir absorbciją.
Jei norime rasti reakcijų rinkinį, kur reikalinga minimali energija, turėsime sugebėti atsižvelgti į šilumos absorbciją kaip neigiamą svorį ir šilumos išsklaidymą kaip teigiamą svorį.
Kodėl turime būti atsargūs su neigiamu svoriu?
Neigiamos svorio briaunos gali sukurti neigiamą svorio ciklą, ty ciklą, kuris sumažins bendrą kelio atstumą grįždamas į tą patį tašką.
Neigiami svorio ciklai gali duoti neteisingą rezultatą bandant išsiaiškinti trumpiausią kelią
Trumpiausi kelio algoritmai, tokie kaip „Dijkstra“ algoritmai, negalintys aptikti tokio ciklo, gali duoti neteisingą rezultatą, nes jie gali pereiti neigiamą svorio ciklą ir sumažinti kelio ilgį.
Kaip veikia Bellmano Fordo algoritmas
Bellmano Fordo algoritmas veikia pervertindamas kelio ilgį nuo pradinės viršūnės iki visų kitų viršūnių. Tada jis pakartoja tuos įvertinimus, ieškodamas naujų kelių, kurie yra trumpesni už anksčiau pervertintus kelius.
Tai darydami pakartotinai visoms viršūnėms, galime garantuoti, kad rezultatas bus optimizuotas.
1 žingsnis Bellman Fordo algoritmui 
2 žingsnis Bellman Ford algoritmui 
3 žingsnis Bellman Fordo algoritmui 
Step-4 Bellman Ford algoritmui 
Step-5 Bellman Ford algoritmui Step-5 Bellman Ford algoritmui 
Step-6 Bellman Ford algoritmui
Bellmanas Fordo pseudokodas
Turime išlaikyti kiekvienos viršūnės kelio atstumą. Mes galime tai laikyti v dydžio masyve, kur v yra viršūnių skaičius.
Mes taip pat norime, kad būtų galima pasiekti trumpiausią kelią, ne tik žinoti trumpiausio kelio ilgį. Tam mes susiejame kiekvieną viršūnę su viršūne, kuri paskutinį kartą atnaujino savo kelio ilgį.
Pasibaigus algoritmui, galime grįžti iš paskirties viršūnės į šaltinio viršūnę, kad rastume kelią.
funkcija bellmanFord (G, S) kiekvienai V viršūnei G atstumu (V) <- begalinis ankstesnis (V) <- NULL atstumas (S) <- 0 kiekvienai V viršūnei G kiekvienam kraštui (U, V) G tempDistance <- atstumas (U) + krašto svoris (U, V), jei tempDistance <atstumas (V) atstumas (V) <- tempDistolis ankstesnis (V) <- U kiekvienam kraštui (U, V), G atstumas (U) + krašto svoris (U, V) <atstumas (V) klaida: neigiamas ciklas yra grįžimo atstumas (), ankstesnis ()
„Bellman Ford“ vs „Dijkstra“
Bellmano Fordo ir Dijkstros algoritmas yra labai panašios struktūros. Nors Dijkstra žvelgia tik į artimiausius viršūnės kaimynus, Bellmanas eina per kiekvieną kraštą kiekvienoje iteracijoje.
Dijkstros ir Bellmano Fordo algoritmas
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
„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; )
Bellmano Fordo sudėtingumas
Laiko kompleksiškumas
| Geriausio atvejo sudėtingumas | O (E) |
| Vidutinis atvejų sudėtingumas | O (VE) |
| Blogiausio atvejo sudėtingumas | O (VE) |
Erdvės sudėtingumas
Erdvės sudėtingumas yra O(V).
Bellmano Fordo algoritmo taikymai
- Skaičiuojant trumpiausius kelius maršruto algoritmuose
- Už trumpiausio kelio paiešką
