Bellman Ford algoritms palīdz mums atrast īsāko ceļu no virsotnes līdz visām pārējām svērtā grafika virsotnēm.
Tas ir līdzīgs Dijkstra algoritmam, bet tas var strādāt ar grafikiem, kuros malām var būt negatīvs svars.
Kāpēc kādreiz dzīvē būtu malas ar negatīvu svaru?
Negatīvās svara malas sākumā var šķist bezjēdzīgas, taču tās var izskaidrot daudzas parādības, piemēram, naudas plūsmu, siltumu, ko atbrīvo / absorbē ķīmiskā reakcija utt.
Piemēram, ja ir dažādi veidi, kā sasniegt vienu ķīmisko vielu A uz citu ķīmisko vielu B, katrai metodei būs apakšreakcijas, kas saistītas gan ar siltuma izkliedi, gan absorbciju.
Ja mēs vēlamies atrast tādu reakciju kopumu, kur nepieciešama minimālā enerģija, tad mums būs jāspēj ņemt vērā siltuma absorbciju kā negatīvus svarus un siltuma izkliedi kā pozitīvus svarus.
Kāpēc mums jābūt uzmanīgiem ar negatīvu svaru?
Negatīvās svara malas var radīt negatīvus svara ciklus, ti, ciklu, kas samazinās kopējo ceļa attālumu, atgriežoties tajā pašā punktā.
Negatīvie svara cikli var dot nepareizu rezultātu, mēģinot noskaidrot īsāko ceļu
Īsākie ceļa algoritmi, piemēram, Dijkstra algoritms, kas nespēj noteikt šādu ciklu, var dot nepareizu rezultātu, jo tie var iziet negatīvu svara ciklu un samazināt ceļa garumu.
Kā darbojas Bellmana Forda algoritms
Bellman Ford algoritms darbojas, pārvērtējot ceļa garumu no sākuma virsotnes līdz visām pārējām virsotnēm. Tad tas iteratīvi atslābina šīs aplēses, atrodot jaunus ceļus, kas ir īsāki nekā iepriekš pārvērtētie ceļi.
Veicot to atkārtoti visām virsotnēm, mēs varam garantēt, ka rezultāts tiek optimizēts.
Step-1 Bellman Ford algoritmam 
Step-2 Bellman Ford algoritmam 
Step-3 Bellman Ford algoritmam 
Step-4 Bellman Ford algoritmam 
Step-5 Bellman Ford algoritmam Step-5 Bellman Ford algoritmam 
Step-6 Bellman Ford algoritmam
Bellman Ford Ford pseidokods
Mums jāsaglabā katras virsotnes ceļa attālums. Mēs to varam uzglabāt v izmēra masīvā, kur v ir virsotņu skaits.
Mēs arī vēlamies, lai būtu iespēja nokļūt īsākajā ceļā, ne tikai zināt īsākā ceļa garumu. Šim nolūkam mēs katru virsotni kartējam ar virsotni, kas pēdējoreiz atjaunināja ceļa garumu.
Kad algoritms ir beidzies, mēs varam atgriezties no galamērķa virsotnes uz avota virsotni, lai atrastu ceļu.
funkcija bellmanFord (G, S) katram V virsotnei G attālumā (V) <- bezgalīgs iepriekšējais (V) <- NULL attālums (S) <- 0 katrai virsotnei V G katrai malai (U, V) G tempDistance <- attālums (U) + malu svars (U, V), ja tempDistance <attālums (V) attālums (V) <- tempDistance iepriekšējais (V) <- U katrai malai (U, V) G Ja attālums (U) + malu svars (U, V) <attālums (V) Kļūda: negatīvs cikls ir atgriešanās attālums (), iepriekšējais ()
Bellman Ford vs Dijkstra
Bellmana Forda un Dijkstra algoritms pēc struktūras ir ļoti līdzīgi. Kamēr Dijkstra skatās tikai uz virsotnes tiešajiem kaimiņiem, Belmens katrā atkārtojumā iziet cauri katrai malai.
Dižkstra vs Bellmana Forda algoritms
Python, Java un C / C ++ piemēri
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; )
Belmana Forda sarežģītība
Laika sarežģītība
| Labākā gadījuma sarežģītība | O (E) |
| Vidējā lietu sarežģītība | O (VE) |
| Sliktākā gadījuma sarežģītība | O (VE) |
Kosmosa sarežģītība
Kosmosa sarežģītība ir O(V).
Belmana Forda algoritma lietojumi
- Īsāko ceļu aprēķināšanai maršrutēšanas algoritmos
- Par īsākā ceļa atrašanu
