Algoritmus Bellman Ford nám pomáhá najít nejkratší cestu od vrcholu ke všem ostatním vrcholům váženého grafu.
Je to podobné jako Dijkstrův algoritmus, ale může pracovat s grafy, ve kterých mohou mít hrany záporné váhy.
Proč by někdo měl v reálném životě hrany se zápornými váhami?
Hrany záporné hmotnosti se na první pohled mohou zdát zbytečné, ale mohou vysvětlit mnoho jevů, jako je cashflow, teplo uvolněné / absorbované chemickou reakcí atd.
Například, pokud existují různé způsoby, jak dosáhnout z jedné chemické látky A na jinou chemickou látku B, bude mít každá metoda dílčí reakce zahrnující jak odvod tepla, tak absorpci.
Pokud chceme najít soubor reakcí, kde je vyžadována minimální energie, pak budeme muset být schopni započítat absorpci tepla jako záporné váhy a rozptyl tepla jako kladné váhy.
Proč si musíme dávat pozor na záporné váhy?
Hrany záporné hmotnosti mohou vytvářet cykly záporné hmotnosti, tj. Cyklus, který sníží celkovou vzdálenost dráhy návratem do stejného bodu.
Negativní váhové cykly mohou při hledání nejkratší cesty způsobit nesprávný výsledek
Nejkratší algoritmy cesty, jako je Dijkstra's Algorithm, které nejsou schopny detekovat takový cyklus, mohou poskytnout nesprávný výsledek, protože mohou projít negativním váhovým cyklem a zkrátit délku cesty.
Jak funguje algoritmus Bellman Ford
Algoritmus Bellman Ford funguje tak, že nadhodnocuje délku cesty od počátečního vrcholu ke všem ostatním vrcholům. Pak tyto odhady iterativně uvolní vyhledáním nových cest, které jsou kratší než dříve nadhodnocené cesty.
Tím, že to uděláme opakovaně pro všechny vrcholy, můžeme zaručit optimalizaci výsledku.
Krok 1 pro algoritmus Bellman Ford 
Krok 2 pro algoritmus Bellman Ford 
Krok 3 pro algoritmus Bellman Ford 
Krok 4 pro algoritmus Bellman Ford 
Krok 5 pro algoritmus Bellman Ford 
Krok 6 pro algoritmus Bellman Ford
Pseudokód Bellman Ford
Musíme udržovat dráhovou vzdálenost každého vrcholu. Můžeme to uložit do pole o velikosti v, kde v je počet vrcholů.
Chceme také mít možnost získat nejkratší cestu, nejen znát délku nejkratší cesty. Za tímto účelem mapujeme každý vrchol na vrchol, který naposledy aktualizoval jeho délku cesty.
Jakmile je algoritmus u konce, můžeme ustoupit od cílového vrcholu ke zdrojovému vrcholu a najít cestu.
funkce bellmanFord (G, S) pro každý vrchol V ve vzdálenosti G (V) <- nekonečná předchozí (V) <- NULL vzdálenost (S) <- 0 pro každý vrchol V v G pro každou hranu (U, V) v G tempDistance <- vzdálenost (U) + edge_weight (U, V) pokud tempDistance <vzdálenost (V) vzdálenost (V) <- tempDistance předchozí (V) <- U pro každou hranu (U, V) v G If vzdálenost (U) + edge_weight (U, V) <distance (V) Error: Negative Cycle Exists return distance (), previous ()
Bellman Ford vs Dijkstra
Algoritmus Bellmana Forda a Dijkstrův algoritmus mají velmi podobnou strukturu. Zatímco Dijkstra vypadá pouze na bezprostřední sousedy vrcholu, Bellman prochází každou hranou v každé iteraci.
Algoritmus Dijkstra vs Bellman Ford
Python, Java a C / C ++ příklady
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žitost společnosti Bellman Ford
Časová složitost
| Nejlepší složitost případu | O (E) |
| Průměrná složitost případu | O (VE) |
| Složitost nejhoršího případu | O (VE) |
Složitost vesmíru
A vesmírná složitost je O(V).
Bellman Ford's Algorithm Applications
- Pro výpočet nejkratších cest ve směrovacích algoritmech
- Pro nalezení nejkratší cesty
