Thuật toán của Bellman Ford

Thuật toán Bellman Ford giúp chúng ta tìm đường đi ngắn nhất từ ​​một đỉnh tới tất cả các đỉnh khác của đồ thị có trọng số.

Nó tương tự như thuật toán Dijkstra nhưng nó có thể hoạt động với các đồ thị trong đó các cạnh có thể có trọng số âm.

Tại sao người ta lại có những cạnh với trọng lượng âm trong đời thực?

Các cạnh trọng lượng âm thoạt đầu có vẻ vô dụng nhưng chúng có thể giải thích rất nhiều hiện tượng như dòng tiền, nhiệt giải phóng / hấp thụ trong phản ứng hóa học, v.v.

Ví dụ, nếu có nhiều cách khác nhau để tiếp cận từ hóa chất A này sang hóa chất B khác, mỗi phương pháp sẽ có các phản ứng phụ liên quan đến tản nhiệt và hấp thụ.

Nếu chúng ta muốn tìm tập hợp các phản ứng trong đó năng lượng tối thiểu là cần thiết, thì chúng ta sẽ cần tính đến sự hấp thụ nhiệt là trọng lượng âm và tản nhiệt là trọng lượng dương.

Tại sao chúng ta cần phải cẩn thận với trọng lượng âm?

Các cạnh trọng lượng âm có thể tạo ra các chu kỳ trọng lượng âm tức là một chu kỳ sẽ làm giảm tổng khoảng cách đường đi bằng cách quay lại cùng một điểm.

Chu kỳ trọng lượng âm có thể cho kết quả không chính xác khi cố gắng tìm ra con đường ngắn nhất

Các thuật toán đường dẫn ngắn nhất như Thuật toán Dijkstra không có khả năng phát hiện một chu trình như vậy có thể đưa ra kết quả không chính xác vì chúng có thể trải qua chu kỳ trọng số âm và giảm độ dài đường dẫn.

Cách thức hoạt động của thuật toán Bellman Ford

Thuật toán Bellman Ford hoạt động bằng cách đánh giá quá cao độ dài của đường đi từ đỉnh xuất phát đến tất cả các đỉnh khác. Sau đó, nó lặp đi lặp lại các ước tính đó bằng cách tìm các đường dẫn mới ngắn hơn các đường dẫn được đánh giá quá cao trước đó.

Bằng cách làm điều này lặp đi lặp lại cho tất cả các đỉnh, chúng tôi có thể đảm bảo rằng kết quả được tối ưu hóa.

Bước-1 cho thuật toán Bellman Ford Bước-2 cho thuật toán Bellman Ford Bước-3 cho thuật toán Bellman Ford Bước-4 cho thuật toán Bellman Ford Bước-5 cho thuật toán Bellman Ford Bước-6 cho thuật toán Bellman Ford

Mã giả Bellman Ford

Chúng ta cần duy trì khoảng cách đường đi của mọi đỉnh. Chúng ta có thể lưu trữ nó trong một mảng có kích thước v, trong đó v là số đỉnh.

Chúng ta cũng muốn có thể đi được con đường ngắn nhất, không chỉ biết độ dài của con đường ngắn nhất. Đối với điều này, chúng tôi ánh xạ mỗi đỉnh đến đỉnh được cập nhật lần cuối cùng độ dài đường dẫn của nó.

Khi thuật toán kết thúc, chúng ta có thể quay ngược lại từ đỉnh đích đến đỉnh nguồn để tìm đường dẫn.

 function bellmanFord (G, S) cho mỗi đỉnh V trong khoảng cách G (V) <- vô hạn trước (V) <- khoảng cách NULL (S) <- 0 cho mỗi đỉnh V trong G cho mỗi cạnh (U, V) trong G tempDistance <- khoảng cách (U) + edge_weight (U, V) nếu tempDistance <khoảng cách (V) khoảng cách (V) <- tempDistance trước đó (V) <- U cho mỗi cạnh (U, V) trong G Nếu khoảng cách (U) + edge_weight (U, V) <distance (V) Error: Negative Cycle Tồn tại khoảng cách trả về (), trước đó ()

Bellman Ford vs Dijkstra

Thuật toán Bellman Ford và thuật toán Dijkstra rất giống nhau về cấu trúc. Trong khi Dijkstra chỉ nhìn vào các hàng xóm trực tiếp của một đỉnh, Bellman đi qua từng cạnh trong mỗi lần lặp lại.

Thuật toán của Dijkstra và Bellman Ford

Ví dụ về Python, Java và 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; )

Sự phức tạp của Bellman Ford

Thời gian phức tạp

Trường hợp phức tạp tốt nhất O (E)
Độ phức tạp của trường hợp trung bình O (VE)
Trường hợp phức tạp tệ nhất O (VE)

Không gian phức tạp

Và, không gian phức tạp là O(V).

Ứng dụng thuật toán của Bellman Ford

  1. Để tính toán đường đi ngắn nhất trong thuật toán định tuyến
  2. Để tìm con đường ngắn nhất

thú vị bài viết...