Algoritam Bellman Ford pomaže nam pronaći najkraći put od vrha do svih ostalih vrhova ponderiranog grafa.
Sličan je Dijkstrinom algoritmu, ali može raditi s grafovima u kojima rubovi mogu imati negativne težine.
Zašto bi netko u stvarnom životu uopće imao rubove s negativnom težinom?
Rubovi negativne težine u početku se mogu činiti beskorisnima, ali mogu objasniti mnoge pojave poput novčanog tijeka, topline koja se oslobađa / apsorbira u kemijskoj reakciji itd.
Na primjer, ako postoje različiti načini kako doći do jedne kemikalije A do druge kemikalije B, svaka metoda imat će podreakcije koje uključuju i rasipanje i apsorpciju topline.
Ako želimo pronaći skup reakcija gdje je potrebna minimalna energija, tada ćemo morati biti u stanju apsorbirati toplinu kao negativne težine, a odvođenje topline kao pozitivne težine.
Zašto trebamo biti oprezni s negativnim utezima?
Rubovi negativne težine mogu stvoriti cikluse negativne težine, tj. Ciklus koji će smanjiti ukupnu udaljenost puta vraćajući se u istu točku.
Negativni ciklusi težine mogu dati netočan rezultat kada se pokušava pronaći najkraći put
Najkraći algoritmi puta poput Dijkstrinog algoritma koji nisu u stanju otkriti takav ciklus mogu dati netočne rezultate jer mogu proći kroz negativni ciklus težine i smanjiti duljinu puta.
Kako funkcionira algoritam Bellmana Forda
Algoritam Bellman Ford djeluje tako što precjenjuje duljinu puta od početnog vrha do svih ostalih vrhova. Tada iterativno ublažava te procjene pronalaženjem novih putova koji su kraći od prethodno precijenjenih putova.
Čineći to više puta za sve vrhove, možemo jamčiti da je rezultat optimiziran.
Korak-1 za algoritam Bellman Ford 
Korak-2 za algoritam Bellman Ford 
Korak-3 za algoritam Bellman Ford 
Korak-4 za algoritam Bellman Ford 
Korak-5 za algoritam Bellman Ford 
Korak-6 za algoritam Bellman Ford
Bellman Ford Pseudocode
Moramo održavati udaljenost puta svakog vrha. To možemo pohraniti u niz veličine v, gdje je v broj vrhova.
Također želimo biti u mogućnosti doći do najkraćeg puta, ne samo da znamo dužinu najkraćeg puta. Zbog toga svaki vrh preslikavamo na vrh koji je zadnji put ažurirao duljinu puta.
Nakon što algoritam završi, možemo se vratiti s odredišnog vrha na izvorni vrh kako bismo pronašli put.
funkcija bellmanFord (G, S) za svaki vrh V u udaljenosti G (V) <- beskonačna prethodna (V) <- NULL udaljenost (S) <- 0 za svaki vrh V u G za svaki rub (U, V) u G tempDistance <- udaljenost (U) + rub_tega (U, V) ako je tempDistance <udaljenost (V) udaljenost (V) <- tempDistance prethodna (V) <- U za svaki rub (U, V) u G Ako udaljenost (U) + edge_weight (U, V) <distance (V) Pogreška: Negativni ciklus postoji povratna udaljenost (), prethodna ()
Bellman Ford vs Dijkstra
Algoritam Bellmana Forda i Dijkstra vrlo su slični u strukturi. Dok Dijkstra gleda samo na neposredne susjede vrha, Bellman prolazi kroz svaki rub u svakoj iteraciji.
Dijkstrin vs Algoritam Bellmana Forda
Primjeri Pythona, Java i 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; )
Složenost Bellmana Forda
Složenost vremena
| Složenost najboljeg slučaja | O (E) |
| Prosječna složenost predmeta | O (VE) |
| Najgora složenost slučaja | O (VE) |
Složenost prostora
I, složenost prostora je O(V).
Primjene algoritma Bellmana Forda
- Za izračunavanje najkraćih putova u algoritmima usmjeravanja
- Za pronalaženje najkraćeg puta
