Algoritma Bellman-Ford
Terakhir diperbarui
Bellman-Ford adalah algoritma untuk mencari jalur terpendek dari satu node sumber ke setiap node lainnya, dan tidak seperti Dijkstra, algoritma ini tetap bekerja meskipun ada bobot edge yang negatif. Caranya adalah relaksasi brute force: algoritma ini berulang kali memindai setiap edge, dan jika melewati edge itu menghasilkan jarak yang lebih pendek, jarak node tujuannya diperbarui. Tekan Putar di atas untuk melihat jarak sementara turun dari putaran ke putaran.
Setelah V - 1 putaran atas semua edge, setiap jalur terpendek (yang paling banyak memiliki V - 1 edge) sudah ditemukan. Karena itu kompleksitasnya O(V · E), lebih lambat daripada Dijkstra, tetapi algoritma ini menangani bobot negatif dan bisa mendeteksi siklus berbobot negatif (jika putaran ke-V masih merelaksasi sebuah edge, jalur terpendek tidak ada).
Kompleksitas waktu dan ruang
| Ukuran | Kompleksitas | Catatan |
|---|---|---|
| Waktu | O(V · E) | V − 1 putaran atas semua E edge |
| Ruang | O(V) | Satu jarak per node |
| Bobot negatif | Didukung | Keunggulan utamanya dibanding Dijkstra |
| Siklus negatif | Bisa dideteksi | Putaran ke-V yang masih merelaksasi menandakan adanya siklus negatif |
Langkah demi langkah
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Atur jarak sumber ke 0 dan semua jarak lainnya ke tak hingga. |
| 2 | Ulangi langkah berikutnya sebanyak V − 1 kali. |
| 3 | Untuk setiap edge (u → v, w), periksa apakah dist[u] + w < dist[v]. |
| 4 | Jika ya, relaksasi edge itu: atur dist[v] = dist[u] + w. |
| 5 | Berhenti lebih awal jika satu putaran penuh tidak mengubah apa pun. |
Contoh penerapan
Sumber S pada 4 node S, A, B, C dengan edge S→A (4), S→B (5), A→C (3), B→A (-3), direlaksasi dalam urutan itu. Jarak dimulai dari S=0 dan sisanya ∞:
| Putaran | Jarak [S, A, B, C] | Aksi |
|---|---|---|
| Awal | [0, ∞, ∞, ∞] | Jarak sumber 0, semua lainnya tak hingga. |
| 1 | [0, 2, 5, 7] | Relaksasi S→A menjadi 4, S→B menjadi 5, A→C menjadi 7, lalu B→A menurunkan A menjadi 5 + (-3) = 2. |
| 2 | [0, 2, 5, 5] | A→C sekarang memperbaiki C menjadi 2 + 3 = 5; tidak ada edge lain yang direlaksasi. |
| 3 | [0, 2, 5, 5] | Tidak ada edge yang direlaksasi, jadi jarak sudah final: A berbiaya 2 lewat S→B→A. |
Kapan memakai Bellman-Ford
| Pakai saat | Hindari saat |
|---|---|
| Bobot edge bisa negatif. | Semua bobot tidak negatif (Dijkstra lebih cepat). |
| Kamu harus mendeteksi siklus berbobot negatif. | Grafnya sangat besar dan padat: O(V · E) terlalu lambat. |
| Grafnya kecil atau renggang. | Kamu hanya butuh satu query dari sumber ke tujuan pada graf yang besar. |
| Kamu butuh pembanding yang sederhana dan mudah diimplementasikan. | Bobotnya tidak negatif dan latensi penting. |
Kode Bellman-Ford Algorithm
Implementasi Bellman-Ford Algorithm yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Bellman-Ford Algorithm dalam Python
Python
1def bellman_ford(vertices, edges, start):2 dist = {v: float("inf") for v in vertices}3 dist[start] = 04 # Relax every edge V-1 times5 for _ in range(len(vertices) - 1):6 for u, v, w in edges:7 if dist[u] + w < dist[v]:8 dist[v] = dist[u] + w9 # One more pass: any improvement means a negative cycle10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 raise ValueError("Graph contains a negative-weight cycle")13 return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18 ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19 ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23 print(f"A -> {node}: {d}")Kode Bellman-Ford Algorithm dalam JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4 ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8 const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9 dist[source] = 0;10 // Relax every edge V-1 times11 for (let i = 0; i < nodes.length - 1; i++) {12 for (const [u, v, w] of edges) {13 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14 }15 }16 // One more pass: any improvement means a negative cycle17 for (const [u, v, w] of edges) {18 if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19 }20 return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));Kode Bellman-Ford Algorithm dalam Java
Java
1import java.util.Arrays;2
3public class Main {4 public static void main(String[] args) {5 int n = 5;6 // Directed edges {from, to, weight}; negative weights allowed7 int[][] edges = {8 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9 {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10 };11 int[] dist = new int[n];12 Arrays.fill(dist, Integer.MAX_VALUE);13 dist[0] = 0;14
15 // Relax every edge V-1 times16 for (int i = 0; i < n - 1; i++) {17 for (int[] e : edges) {18 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19 dist[e[1]] = dist[e[0]] + e[2];20 }21 }22 }23
24 // One more pass: any improvement means a negative cycle25 boolean hasNegativeCycle = false;26 for (int[] e : edges) {27 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28 hasNegativeCycle = true;29 }30 }31
32 System.out.println("Distances from 0: " + Arrays.toString(dist));33 System.out.println("Negative cycle: " + hasNegativeCycle);34 }35}Kode Bellman-Ford Algorithm dalam C++
C++
1#include <iostream>2#include <vector>3
4struct Edge {5 int from, to, weight;6};7
8int main() {9 const int INF = 1000000000;10 const int n = 5;11 std::vector<Edge> edges = {12 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14 };15 std::vector<int> dist(n, INF);16 dist[0] = 0;17 // Relax every edge V-1 times18 for (int pass = 0; pass < n - 1; ++pass) {19 for (const Edge& e : edges) {20 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21 dist[e.to] = dist[e.from] + e.weight;22 }23 }24 }25 // One extra pass: any improvement means a negative cycle26 bool negativeCycle = false;27 for (const Edge& e : edges) {28 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29 negativeCycle = true;30 }31 }32 if (negativeCycle) {33 std::cout << "Negative cycle detected\n";34 } else {35 for (int v = 0; v < n; ++v) {36 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37 }38 }39 return 0;40}Kode Bellman-Ford Algorithm dalam C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8 int from, to, weight;9} Edge;10
11int main(void) {12 Edge edges[] = {13 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15 };16 int m = sizeof(edges) / sizeof(edges[0]);17 int dist[N];18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // Relax every edge V-1 times21 for (int pass = 0; pass < N - 1; pass++) {22 for (int i = 0; i < m; i++) {23 Edge e = edges[i];24 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25 dist[e.to] = dist[e.from] + e.weight;26 }27 }28 }29 // One extra pass: any improvement means a negative cycle30 bool negativeCycle = false;31 for (int i = 0; i < m; i++) {32 Edge e = edges[i];33 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34 negativeCycle = true;35 }36 }37 if (negativeCycle) {38 printf("Negative cycle detected\n");39 } else {40 for (int v = 0; v < N; v++) {41 printf("Distance 0 -> %d: %d\n", v, dist[v]);42 }43 }44 return 0;45}FAQ Bellman-Ford
Berapa kompleksitas waktu Bellman-Ford?
Bellman-Ford berjalan dalam waktu
O(V · E): algoritma ini melakukan V - 1 putaran, dan setiap putaran merelaksasi semua E edge. Itu lebih lambat daripada O((V + E) log V) milik Dijkstra, dan itulah harga dari dukungan untuk bobot edge negatif.Kapan sebaiknya memakai Bellman-Ford, bukan Dijkstra?
Pakai Bellman-Ford saat graf bisa memiliki bobot edge negatif, atau saat kamu perlu mendeteksi siklus berbobot negatif. Dijkstra lebih cepat, tetapi hanya benar untuk bobot yang tidak negatif. Contoh penggunaan nyata yang umum adalah mendeteksi peluang arbitrase penukaran mata uang, di mana siklus negatif berperan penting.
Bagaimana Bellman-Ford mendeteksi siklus negatif?
Setelah
V - 1 putaran relaksasi, semua jalur terpendek sudah final jika tidak ada siklus negatif. Jika satu putaran tambahan masih bisa merelaksasi sebuah edge, berarti ada siklus berbobot negatif yang bisa dicapai, dan jalur terpendek tidak terdefinisi (kamu bisa terus berputar untuk menurunkan biayanya).Apa perbedaan Bellman-Ford dan Floyd-Warshall?
Bellman-Ford menghitung jalur terpendek dari satu sumber dalam
O(V · E), sedangkan Floyd-Warshall menghitung jalur terpendek untuk semua pasangan dalam O(V³). Pada graf yang padat, menjalankan Bellman-Ford dari setiap sumber berbiaya O(V² · E), jadi Floyd-Warshall biasanya pilihan yang lebih baik saat kamu butuh setiap pasangan. Keduanya menangani edge negatif dan bisa menandai siklus negatif.Mengapa Bellman-Ford butuh tepat V - 1 putaran?
Setiap jalur terpendek pada graf tanpa siklus negatif memakai paling banyak
V - 1 edge, karena jalur yang mengunjungi lebih dari V node pasti mengulang salah satunya. Setiap putaran menjamin minimal satu edge tambahan dari setiap jalur terpendek direlaksasi dengan benar, jadi V - 1 putaran sudah cukup untuk menuntaskan semuanya. Salah kaprah yang umum adalah anggapan bahwa putaran tambahan memperbaiki jawabannya. Itu tidak pernah terjadi, kecuali ada siklus negatif.Bisakah Bellman-Ford berhenti lebih awal?
Bisa. Jika satu putaran penuh atas semua edge tidak merelaksasi apa pun, setiap jarak sudah optimal dan kamu bisa berhenti sebelum mencapai
V - 1 putaran. Optimasi keluar lebih awal ini sering membuatnya jauh lebih cepat pada graf yang cepat mengerucut, meskipun batas kasus terburuknya tetap O(V · E).Sumber terkait
Visualisasi lainnya
