Algoritma Bellman-Ford
- Diperkenalkan oleh
- Richard Bellman and Lester R. Ford
- Tahun
- 1956
- Jenis
- algorithm
- Keluarga
- Graph Algorithms
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Algoritma Bellman-Ford, dikembangkan oleh Richard Bellman dan Lester R. Ford pada tahun 1950-an, adalah algoritma fundamental untuk menghitung jalur terpendek dalam graf berbobot yang mungkin mengandung bobot sisi negatif.
Berbeda dengan algoritma Dijkstra, algoritma ini menangani bobot negatif dengan benar dan dapat mendeteksi keberadaan siklus berbobot negatif.
Intuisi di balik metode
Algoritma bekerja dengan mengendurkan sisi secara iteratif: untuk setiap sisi, ia memeriksa apakah melewati sisi tersebut menawarkan jalur yang lebih pendek ke tujuan daripada jalur terbaik yang diketahui saat ini. Dengan mengulangi proses ini untuk semua sisi sebanyak V-1 kali, di mana V adalah jumlah simpul, algoritma menjamin penemuan jalur terpendek bahkan dengan bobot negatif. Wawasan kuncinya adalah bahwa setiap jalur terpendek dalam graf dengan V simpul berisi paling banyak V-1 sisi; jika jarak masih membaik setelah V-1 iterasi, siklus negatif pasti ada.
Sejarah
Richard Bellman mengembangkan algoritma pada tahun 1958 menggunakan prinsip pemrograman dinamis, sementara Lester R. Ford secara independen menemukan pendekatan serupa untuk aliran jaringan pada tahun 1956. Algoritma ini lebih lanjut dikembangkan dan ditingkatkan pada tahun 1960-an, dengan aplikasi meluas ke perutean jaringan dan aplikasi ekonomi. Varian modern termasuk Algoritma Jalur Terpendek Lebih Cepat (SPFA) dan berbagai optimasi untuk struktur graf tertentu, meskipun pendekatan dasar Bellman-Ford tetap menjadi referensi klasik dalam desain algoritma.
Kapan digunakan
Terapkan algoritma Bellman-Ford saat menghitung jalur terpendek dalam graf dengan bobot sisi negatif. Ini penting untuk deteksi arbitrase mata uang, protokol jaringan di mana bobot bisa negatif, dan aplikasi apa pun di mana biaya atau bobot negatif bermakna. Gunakan algoritma Dijkstra jika semua bobot non-negatif, karena lebih efisien. Untuk mendeteksi siklus negatif tanpa menghitung jalur, algoritma ini juga sesuai.
Batasan dan pertimbangan
- Lebih lambat daripada Dijkstra untuk bobot non-negatif: O(VE) versus O((V+E)logV)
- Kurang efisien untuk graf renggang dibandingkan algoritma lain
- Membutuhkan semua sisi untuk terdaftar secara eksplisit, membuatnya kurang cocok untuk graf implisit atau dinamis
- Tidak ada panduan heuristik yang tersedia untuk mempercepat komputasi
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menangani graf dengan bobot sisi negatif dengan benar
- Mendeteksi siklus berbobot negatif, mencegah hasil jalur terpendek yang keliru
- Lebih sederhana untuk dipahami dan diimplementasikan daripada beberapa algoritma jalur terpendek tingkat lanjut
- Dijamin menemukan jalur terpendek dalam waktu O(VE)
- Bekerja pada graf berarah dan tak berarah (dengan hati-hati pada tak berarah)
Penerapan
- Deteksi arbitrase mata uang: mengidentifikasi siklus yang menguntungkan dalam graf nilai tukar
- Protokol perutean jaringan: menghitung jalur terpendek di mana biaya tautan dapat bervariasi atau negatif
- Teori permainan: menyelesaikan masalah jalur terpendek dengan sisi penalti atau faktor diskon
- Robotika: perencanaan jalur di lingkungan dengan gaya tolak (bobot negatif)
- Pemesanan ekonomi: mengoptimalkan pembangkitan daya dengan fungsi biaya termasuk suku negatif
- Telekomunikasi: menemukan rute optimal ketika bobot tautan mewakili metrik penundaan atau kualitas
Cara kerjanya
Cara kerjanya
Tetapkan jarak ke sumber sebagai nol dan semua jarak lainnya sebagai tak terhingga; secara opsional, tetapkan semua pendahulu sebagai null.
Ulangi V-1 kali: untuk setiap sisi (u, v) dengan bobot w, jika jarak[u] + w lebih kecil dari jarak[v], perbarui jarak[v] dan pendahulu v.
Periksa semua sisi sekali lagi; jika ada jarak yang membaik, ada siklus berbobot negatif. Kembalikan kesalahan atau identifikasi siklus sesuai kebutuhan.
Kesalahan umum
- Lupa melakukan iterasi tambahan untuk mendeteksi siklus negatif
- Mengasumsikan algoritma bekerja dengan benar pada graf tak berarah dengan sisi negatif (dapat membuat siklus negatif virtual)
- Menggunakan algoritma ketika Dijkstra sudah cukup, menghasilkan kehilangan kinerja yang tidak perlu
Pertanyaan yang sering diajukan
Mengapa algoritma membutuhkan tepat V-1 iterasi?
Setiap jalur dalam graf dengan V simpul memiliki paling banyak V-1 sisi. Dengan mengulang V-1 kali, algoritma memungkinkan informasi jarak menyebar ke seluruh graf. Iterasi ke-V hanya akan meningkatkan jarak jika ada siklus negatif.
Bagaimana algoritma dapat mendeteksi siklus negatif?
Setelah menyelesaikan V-1 iterasi, jalankan satu putaran relaksasi lagi. Jika ada jarak yang berkurang, ada siklus negatif. Simpul yang terlibat dalam siklus dapat diidentifikasi melalui penelusuran mundur menggunakan penunjuk pendahulu.
Berapa kompleksitas waktu dan bagaimana perbandingannya dengan Dijkstra?
Bellman-Ford berjalan dalam waktu O(VE), di mana V adalah simpul dan E adalah sisi. Dijkstra berjalan dalam O((V+E)logV) dengan heap biner. Bellman-Ford lebih lambat tetapi menangani bobot negatif; Dijkstra lebih cepat tetapi membutuhkan bobot non-negatif.
Bisakah Bellman-Ford bekerja pada graf tak berarah dengan bobot negatif?
Secara teknis ya, tetapi dapat menciptakan siklus negatif palsu karena sifat dua arah dari sisi. Perhatian khusus diperlukan untuk menafsirkan hasil dengan benar. Untuk graf tak berarah, pertimbangkan pendekatan alternatif.
Metode terkait
Sumber
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
Buka referensi DOIDisalin.Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.
Buka referensi publikasiDisalin.