Algoritmul Bellman Ford ne ajută să găsim cea mai scurtă cale de la un vârf la toate celelalte vârfuri ale unui grafic ponderat.
Este similar cu algoritmul lui Dijkstra, dar poate funcționa cu grafice în care muchiile pot avea greutăți negative.
De ce ar avea vreodată margini cu greutăți negative în viața reală?
Marginile negative ale greutății ar putea părea inutile la început, dar pot explica o mulțime de fenomene precum fluxul de numerar, căldura eliberată / absorbită într-o reacție chimică etc.
De exemplu, dacă există modalități diferite de a ajunge de la o substanță chimică A la o altă substanță chimică B, fiecare metodă va avea sub-reacții care implică atât disiparea căldurii, cât și absorbția.
Dacă dorim să găsim setul de reacții în care este necesară o energie minimă, atunci va trebui să putem lua în calcul absorbția căldurii ca greutăți negative și disiparea căldurii ca greutăți pozitive.
De ce trebuie să fim atenți la greutăți negative?
Marginile de greutate negative pot crea cicluri de greutate negative, adică un ciclu care va reduce distanța totală a traseului revenind în același punct.
Ciclurile de greutate negative pot da un rezultat incorect atunci când încercăm să aflăm calea cea mai scurtă
Cei mai scurți algoritmi de cale, cum ar fi algoritmul lui Dijkstra, care nu sunt capabili să detecteze un astfel de ciclu pot da un rezultat incorect, deoarece pot trece printr-un ciclu de greutate negativ și pot reduce lungimea căii.
Cum funcționează algoritmul lui Bellman Ford
Algoritmul Bellman Ford funcționează supraestimând lungimea căii de la vârful de pornire la toate celelalte vârfuri. Apoi relaxează iterativ acele estimări găsind căi noi care sunt mai scurte decât căile supraevaluate anterior.
Procedând în mod repetat pentru toate vârfurile, putem garanta că rezultatul este optimizat.
Pasul 1 pentru algoritmul lui Bellman Ford 
Pasul 2 pentru algoritmul lui Bellman Ford 
Pasul 3 pentru algoritmul lui Bellman Ford 
Pasul 4 pentru algoritmul lui Bellman Ford 
Pasul 5 pentru algoritmul lui Bellman Ford 
Pasul 6 pentru algoritmul lui Bellman Ford
Bellman Ford Pseudocode
Trebuie să menținem distanța de cale a fiecărui vârf. Putem stoca asta într-o matrice de dimensiunea v, unde v este numărul de vârfuri.
De asemenea, dorim să putem obține cea mai scurtă cale, nu numai să știm lungimea celei mai scurte căi. Pentru aceasta, mapăm fiecare vârf la vârful care și-a actualizat ultima dată lungimea căii.
Odată ce algoritmul s-a terminat, putem retrograda de la vârful destinației la vârful sursă pentru a găsi calea.
funcție bellman Ford (G, S) pentru fiecare vârf V în distanță G (V) <- precedent infinit (V) <- distanță NULL (S) <- 0 pentru fiecare vârf V în G pentru fiecare margine (U, V) în G tempDistance <- distance (U) + edge_weight (U, V) if tempDistance <distance (V) distance (V) <- tempDistance previous (V) <- U for each edge (U, V) in G If distance (U) + edge_weight (U, V) <distanță (V) Eroare: ciclu negativ Exista distanta de retur (), precedent ()
Bellman Ford vs Dijkstra
Algoritmul lui Bellman Ford și algoritmul lui Dijkstra sunt foarte asemănătoare ca structură. În timp ce Dijkstra privește doar vecinii imediați ai unui vârf, Bellman trece prin fiecare margine în fiecare iterație.
Algoritmul lui Dijkstra împotriva lui Bellman Ford
Exemple Python, 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; )
Complexitatea lui Bellman Ford
Complexitatea timpului
| Complexitatea celui mai bun caz | O (E) |
| Complexitatea medie a cazurilor | O (VE) |
| Cel mai prost caz de complexitate | O (VE) |
Complexitatea spațială
Și complexitatea spațiului este O(V).
Aplicațiile algoritmului Bellman Ford
- Pentru calcularea celor mai scurte căi în algoritmi de rutare
- Pentru găsirea celei mai scurte căi
