Algoritma Bellman Ford membantu kita menemukan jalur terpendek dari sebuah simpul ke semua simpul lain dari sebuah graf berbobot.
Ini mirip dengan algoritma Dijkstra tetapi dapat bekerja dengan grafik di mana tepi dapat memiliki bobot negatif.
Mengapa seseorang pernah memiliki tepi dengan bobot negatif dalam kehidupan nyata?
Tepi berbobot negatif mungkin tampak tidak berguna pada awalnya tetapi mereka dapat menjelaskan banyak fenomena seperti arus kas, panas yang dilepaskan / diserap dalam reaksi kimia, dll.
Misalnya, jika ada cara berbeda untuk menjangkau dari satu bahan kimia A ke bahan kimia B lainnya, setiap metode akan memiliki sub-reaksi yang melibatkan pembuangan dan penyerapan panas.
Jika kita ingin mencari himpunan reaksi yang memerlukan energi minimum, kita perlu memperhitungkan penyerapan panas sebagai bobot negatif dan disipasi panas sebagai bobot positif.
Mengapa kita perlu berhati-hati dengan bobot negatif?
Tepi berbobot negatif dapat membuat siklus berbobot negatif yaitu siklus yang akan mengurangi total jarak jalur dengan kembali ke titik yang sama.
Siklus berbobot negatif dapat memberikan hasil yang salah saat mencoba mencari jalur terpendek
Algoritma jalur terpendek seperti Algoritma Dijkstra yang tidak dapat mendeteksi siklus tersebut dapat memberikan hasil yang salah karena dapat melalui siklus berbobot negatif dan mengurangi panjang jalur.
Bagaimana algoritma Bellman Ford bekerja
Algoritma Bellman Ford bekerja dengan melebih-lebihkan panjang jalur dari simpul awal ke semua simpul lainnya. Kemudian secara berulang melonggarkan estimasi tersebut dengan menemukan jalur baru yang lebih pendek dari jalur yang sebelumnya ditaksir terlalu tinggi.
Dengan melakukan ini berulang kali untuk semua simpul, kami dapat menjamin bahwa hasilnya dioptimalkan.
Langkah-1 untuk algoritma Bellman Ford 
Langkah-2 untuk algoritma Bellman Ford 
Langkah-3 untuk algoritma Bellman Ford 
Langkah-4 untuk algoritma Bellman Ford 
Langkah-5 untuk algoritma Bellman Ford 
Langkah-6 untuk algoritma Bellman Ford
Kode Pseudocode Bellman Ford
Kita perlu mempertahankan jarak jalur setiap simpul. Kita bisa menyimpannya dalam larik berukuran v, di mana v adalah jumlah simpul.
Kami juga ingin bisa mendapatkan jalur terpendek, tidak hanya mengetahui panjang jalur terpendek. Untuk ini, kami memetakan setiap simpul ke simpul yang terakhir memperbarui panjang jalurnya.
Setelah algoritme selesai, kita dapat mundur dari simpul tujuan ke simpul sumber untuk menemukan jalurnya.
function bellmanFord (G, S) untuk tiap simpul V di G jarak (V) <- tak terhingga sebelumnya (V) <- NULL jarak (S) <- 0 untuk tiap simpul V di G untuk tiap sisi (U, V) di G tempDistance <- jarak (U) + edge_weight (U, V) jika tempDistance <jarak (V) jarak (V) <- tempDistance sebelumnya (V) <- U untuk setiap sisi (U, V) di G Jika jarak (U) + edge_weight (U, V) <distance (V) Error: Siklus Negatif Ada jarak kembali (), sebelumnya ()
Bellman Ford vs Dijkstra
Algoritma Bellman Ford dan algoritma Dijkstra memiliki struktur yang sangat mirip. Sementara Dijkstra hanya melihat ke tetangga terdekat dari sebuah simpul, Bellman melewati setiap sisi di setiap iterasi.
Algoritma Dijkstra vs Bellman Ford
Contoh Python, Java dan C / C ++
Python Java 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; )
Kompleksitas Bellman Ford
Kompleksitas Waktu
| Kompleksitas Kasus Terbaik | O (E) |
| Kompleksitas Kasus Rata-rata | O (VE) |
| Kompleksitas Kasus Terburuk | O (VE) |
Kompleksitas Ruang
Dan, kompleksitas ruangnya O(V).
Aplikasi Algoritma Bellman Ford
- Untuk menghitung jalur terpendek dalam algoritma perutean
- Untuk menemukan jalur terpendek
