Алгоритм Беллмана Форда помогает найти кратчайший путь от вершины ко всем остальным вершинам взвешенного графа.
Он похож на алгоритм Дейкстры, но может работать с графами, в которых ребра могут иметь отрицательные веса.
Зачем вообще иметь края с отрицательным весом в реальной жизни?
Поначалу отрицательные грани веса могут показаться бесполезными, но они могут объяснить многие явления, такие как денежный поток, тепло, выделяемое / поглощаемое в химической реакции и т. Д.
Например, если существуют разные способы перехода от одного химического вещества A к другому химическому веществу B, каждый метод будет иметь дополнительные реакции, включающие как рассеивание, так и поглощение тепла.
Если мы хотим найти набор реакций, для которых требуется минимальная энергия, тогда нам нужно будет учесть поглощение тепла как отрицательные веса и рассеивание тепла как положительные веса.
Почему нужно быть осторожным с отрицательными весами?
Ребра с отрицательным весом могут создавать циклы с отрицательным весом, то есть цикл, который уменьшит общее расстояние пути, возвращаясь к той же точке.
Циклы с отрицательным весом могут дать неверный результат при поиске кратчайшего пути.
Алгоритмы кратчайшего пути, такие как алгоритм Дейкстры, которые не могут обнаружить такой цикл, могут дать неверный результат, потому что они могут пройти цикл с отрицательным весом и уменьшить длину пути.
Как работает алгоритм Беллмана Форда
Алгоритм Беллмана-Форда работает, переоценивая длину пути от начальной вершины до всех остальных вершин. Затем он итеративно ослабляет эти оценки, находя новые пути, которые короче, чем ранее оцененные пути.
Делая это многократно для всех вершин, мы можем гарантировать, что результат будет оптимизирован.
Шаг 1 для алгоритма Беллмана Форда 
Шаг 2 для алгоритма Беллмана Форда 
Шаг 3 для алгоритма Беллмана Форда 
Шаг 4 для алгоритма Беллмана Форда 
Шаг 5 для алгоритма Беллмана Форда 
Шаг 6 для алгоритма Беллмана Форда
Bellman Ford Псевдокод
Нам нужно поддерживать путь до каждой вершины. Мы можем сохранить это в массиве размера v, где v - количество вершин.
Мы также хотим иметь возможность получить кратчайший путь, а не только знать длину кратчайшего пути. Для этого мы сопоставляем каждую вершину с вершиной, которая последней обновила свой путь.
После завершения алгоритма мы можем вернуться от целевой вершины к исходной вершине, чтобы найти путь.
функция bellmanFord (G, S) для каждой вершины V в G distance (V) <- бесконечное предыдущее (V) <- NULL distance (S) <- 0 для каждой вершины V в G для каждого ребра (U, V) в G tempDistance <- distance (U) + edge_weight (U, V) if tempDistance <distance (V) distance (V) <- tempDistance previous (V) <- U для каждого края (U, V) в G Если расстояние (U) + edge_weight (U, V) <distance (V) Ошибка: существует отрицательный цикл, расстояние возврата (), previous ()
Беллман Форд против Дейкстры
Алгоритм Беллмана Форда и алгоритм Дейкстры очень похожи по структуре. В то время как Дейкстра смотрит только на непосредственных соседей вершины, Беллман просматривает каждое ребро на каждой итерации.
Алгоритм Дейкстры против Беллмана Форда
Примеры Python, Java и 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; )
Сложность Беллмана Форда
Сложность времени
| Лучшая сложность дела | O (E) |
| Средняя сложность дела | O (VE) |
| Сложность наихудшего случая | O (VE) |
Космическая сложность
А космическая сложность есть O(V).
Приложения алгоритма Беллмана Форда
- Для расчета кратчайших путей в алгоритмах маршрутизации
- Для поиска кратчайшего пути
