Algoritma Bellman Ford membantu kami mencari jalan terpendek dari bucu ke semua bucu graf berwajaran lain.
Ia serupa dengan algoritma Dijkstra tetapi boleh berfungsi dengan grafik di mana tepi boleh mempunyai bobot negatif.
Mengapa seseorang mempunyai kelebihan dengan berat negatif dalam kehidupan sebenar?
Berat badan negatif mungkin kelihatan tidak berguna pada mulanya tetapi mereka dapat menjelaskan banyak fenomena seperti aliran tunai, haba yang dilepaskan / diserap dalam tindak balas kimia, dll.
Sebagai contoh, jika ada cara yang berbeza untuk mencapai dari satu bahan kimia ke bahan kimia yang lain, setiap kaedah akan mempunyai sub-tindak balas yang melibatkan penyebaran haba dan penyerapan.
Sekiranya kita ingin mencari kumpulan tindak balas di mana tenaga minimum diperlukan, maka kita perlu dapat memperhitungkan penyerapan haba sebagai bobot negatif dan pelesapan haba sebagai bobot positif.
Mengapa kita perlu berhati-hati dengan bobot negatif?
Tepi berat negatif dapat membuat kitaran berat negatif iaitu kitaran yang akan mengurangkan jarak jarak keseluruhan dengan kembali ke titik yang sama.
Kitaran berat badan negatif dapat memberikan hasil yang salah ketika berusaha mencari jalan terpendek
Algoritma jalan terpendek seperti Algoritma Dijkstra yang tidak dapat mengesan kitaran seperti itu dapat memberikan hasil yang salah kerana mereka dapat melalui kitaran berat negatif dan mengurangkan panjang lintasan.
Bagaimana algoritma Bellman Ford berfungsi
Algoritma Bellman Ford berfungsi dengan mengira terlalu jauh panjang jalan dari bucu permulaan ke semua bucu lain. Kemudian secara berkala melonggarkan anggaran tersebut dengan mencari jalan baru yang lebih pendek daripada jalan yang terlalu tinggi sebelumnya.
Dengan melakukan ini berulang kali untuk semua bucu, kita dapat menjamin hasilnya dioptimumkan.
Langkah-1 untuk algoritma Bellman Ford 
Langkah-2 untuk algoritma Bellman Ford Langkah-2 untuk algoritma Bellman Ford 
Langkah-3 untuk algoritma 
Bellman Ford 
Langkah-2 untuk algoritma Bellman Ford 
Langkah-6 untuk algoritma Bellman Ford
Bellman Ford Pseudocode
Kita perlu mengekalkan jarak laluan setiap bucu. Kita boleh menyimpannya dalam pelbagai ukuran v, di mana v adalah bilangan bucu.
Kami juga ingin mendapatkan jalan terpendek, bukan hanya mengetahui panjang jalan terpendek. Untuk ini, kami memetakan setiap bucu ke bucu yang terakhir mengemas kini panjang lintasannya.
Setelah algoritma selesai, kita dapat mundur dari titik tujuan ke bucu sumber untuk mencari jalan.
fungsi bellmanFord (G, S) untuk setiap bucu V dalam jarak G (V) <- sebelumnya tak terhingga (V) <- jarak NULL (S) <- 0 untuk setiap bucu V di G untuk setiap tepi (U, V) di G tempDistance <- jarak (U) + tepi_berat (U, V) jika tempDistance <jarak (V) jarak (V) <- tempDistance sebelumnya (V) <- U untuk setiap tepi (U, V) di G Jika jarak (U) + edge_weight (U, V) <jarak (V) Ralat: Kitaran Negatif Ada jarak kembali (), sebelumnya ()
Bellman Ford vs Dijkstra
Algoritma Bellman Ford dan algoritma Dijkstra sangat serupa dalam struktur. Walaupun Dijkstra hanya melihat kepada jiran sebelah kanan, Bellman melalui setiap sisi dalam setiap lelaran.
Algoritma Dijkstra vs Bellman Ford
Contoh Python, Java dan 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; )
Kerumitan Bellman Ford
Kerumitan Masa
| Kerumitan Kes Terbaik | O (E) |
| Kerumitan Kes Purata | O (VE) |
| Kerumitan Kes Terburuk | O (VE) |
Kerumitan Ruang
Dan, kerumitan ruang adalah O(V).
Aplikasi Algoritma Bellman Ford
- Untuk mengira laluan terpendek dalam algoritma penghalaan
- Untuk mencari jalan terpendek
