Algorytm Bellmana Forda pomaga nam znaleźć najkrótszą ścieżkę od wierzchołka do wszystkich innych wierzchołków ważonego grafu.
Jest podobny do algorytmu Dijkstry, ale może współpracować z wykresami, w których krawędzie mogą mieć ujemne wagi.
Dlaczego w prawdziwym życiu ktoś miałby mieć krawędzie z ujemnymi wagami?
Ujemne krawędzie wagi mogą początkowo wydawać się bezużyteczne, ale mogą wyjaśniać wiele zjawisk, takich jak przepływ gotówki, ciepło uwalniane / pochłaniane w reakcji chemicznej itp.
Na przykład, jeśli istnieją różne sposoby dotarcia z jednej substancji chemicznej A do drugiej substancji chemicznej B, każda metoda będzie miała podreakcje obejmujące zarówno rozpraszanie, jak i pochłanianie ciepła.
Jeśli chcemy znaleźć zestaw reakcji, w których wymagana jest minimalna energia, będziemy musieli uwzględnić pochłanianie ciepła jako wagi ujemne i rozpraszanie ciepła jako wagi dodatnie.
Dlaczego musimy uważać na wagi ujemne?
Ujemne krawędzie wagi mogą tworzyć ujemne cykle wagi, tj. Cykl, który zmniejszy całkowitą odległość ścieżki poprzez powrót do tego samego punktu.
Ujemne cykle masy mogą dać nieprawidłowy wynik podczas próby znalezienia najkrótszej ścieżki
Algorytmy najkrótszej ścieżki, takie jak algorytm Dijkstry, które nie są w stanie wykryć takiego cyklu, mogą dać niepoprawny wynik, ponieważ mogą przejść przez cykl o ujemnej wadze i zmniejszyć długość ścieżki.
Jak działa algorytm Bellmana Forda
Algorytm Bellmana Forda działa na zasadzie przeszacowania długości ścieżki od początkowego wierzchołka do wszystkich innych wierzchołków. Następnie iteracyjnie rozluźnia te oszacowania, znajdując nowe ścieżki, które są krótsze niż ścieżki poprzednio przeszacowane.
Robiąc to wielokrotnie dla wszystkich wierzchołków, możemy zagwarantować, że wynik jest zoptymalizowany.
Krok-1 dla algorytmu Bellmana Forda 
Krok-2 dla algorytmu Bellmana Forda 
Krok-3 dla algorytmu Bellmana Forda 
Krok-4 dla algorytmu Bellmana Forda 
Krok-5 dla algorytmu Bellmana Forda 
Krok-6 dla algorytmu Bellmana Forda
Pseudokod Bellmana Forda
Musimy zachować odległość ścieżki każdego wierzchołka. Możemy to zapisać w tablicy o rozmiarze v, gdzie v jest liczbą wierzchołków.
Chcemy również móc uzyskać najkrótszą ścieżkę, a nie tylko znać długość najkrótszej ścieżki. W tym celu mapujemy każdy wierzchołek do wierzchołka, który ostatnio zaktualizował jego długość ścieżki.
Po zakończeniu algorytmu możemy cofnąć się od wierzchołka docelowego do wierzchołka źródłowego, aby znaleźć ścieżkę.
function bellmanFord (G, S) dla każdego wierzchołka V w G odległość (V) <- nieskończona poprzednia (V) <- NULL odległość (S) <- 0 dla każdego wierzchołka V w G dla każdej krawędzi (U, V) w G tempDistance <- odległość (U) + edge_weight (U, V) jeśli tempDistance <odległość (V) distance (V) <- temp Distance poprzednia (V) <- U dla każdej krawędzi (U, V) w G Jeśli odległość (U) + edge_weight (U, V) <odległość (V) Błąd: cykl ujemny istnieje powrót odległość (), poprzedni ()
Bellman Ford vs Dijkstra
Algorytm Bellmana Forda i algorytm Dijkstry mają bardzo podobną strukturę. Podczas gdy Dijkstra patrzy tylko na bezpośrednich sąsiadów wierzchołka, Bellman przechodzi przez każdą krawędź w każdej iteracji.
Algorytm Dijkstry vs Algorytm Bellmana Forda
Przykłady w Pythonie, Javie 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; )
Złożoność Bellmana Forda
Złożoność czasowa
| Najlepsza złożoność przypadku | O (E) |
| Średnia złożoność przypadku | O (VE) |
| Najgorsza złożoność przypadku | O (VE) |
Złożoność przestrzeni
A złożoność przestrzeni O(V).
Aplikacje algorytmu Bellmana Forda
- Do obliczania najkrótszych ścieżek w algorytmach routingu
- Za znalezienie najkrótszej ścieżki
