Algoritma Bellman–Ford
Beberapa masalah jalur terpendek punya sisi yang membuat jalur lebih murah: pengembalian dana, jalan menurun, kurs yang menguntungkan Anda. Algoritma Dijkstra tidak sanggup menanganinya. Algoritma Bellman–Ford sanggup, dengan menukar kecerdikan dengan kesabaran.
Idenya
Setiap algoritma jalur terpendek bergantung pada satu gerakan, merelaksasi sisi: jika pergi ke u lalu lewat sisi u → v lebih pendek dari jalan terbaik yang diketahui ke v, pakai jalan itu. Algoritma Dijkstra merelaksasi tiap sisi sekali, dalam urutan cerdik yang hanya berhasil jika tidak ada sisi negatif. Bellman–Ford tidak membuat anggapan itu. Ia merelaksasi setiap sisi, dalam urutan tetap apa pun, berulang kali, sampai jarak berhenti berubah.
Langkah demi langkah
Beri simpul awal jarak 0 dan semua simpul lain tak hingga. Ulangi n − 1 kali, untuk n simpul: telusuri setiap sisi u → v dan relaksasi jika u punya jarak. Berhenti lebih awal jika satu putaran penuh tidak mengubah apa pun. Lalu jalankan satu putaran lagi. Jika masih ada sisi yang bisa direlaksasi, ada siklus dengan total negatif yang bisa dicapai dari awal; jika tidak, setiap jarak sudah terpendek, dan simpul yang diingat memberikan jalurnya.
Contoh
Ambil sisi satu arah A → B dengan panjang 4, A → C 5, B → D 2, dan C → B −3, diperiksa dalam urutan itu, dari A. Putaran 1 memberi B 4, C 5, dan D 6, lalu C → B menurunkan B menjadi 5 − 3 = 2. Putaran 2 menurunkan D menjadi 2 + 2 = 4. Putaran 3 tidak mengubah apa pun, jadi jawabannya B 2, C 5, D 4. Algoritma Dijkstra akan membuat B final di 4 dan D di 6, sebelum melihat sisi negatif. Tambahkan sisi D → C dengan panjang −4, dan siklus C → B → D → C berjumlah −5: setiap putaran menurunkan jarak lagi, dan putaran pemeriksaan melaporkannya.
Mengapa n − 1 putaran cukup
Jalur terpendek, jika ada, tidak pernah mengulang simpul, jadi punya paling banyak n − 1 sisi. Merelaksasi setiap sisi dalam satu putaran memperpanjang setiap jalur terpendek yang sudah diketahui dengan benar sebanyak satu sisi lagi, apa pun urutan sisinya. Jadi setelah putaran k, semua jalur terpendek dengan sampai k sisi sudah benar, dan setelah n − 1 putaran, semuanya. Urutan tetap berpengaruh pada kecepatan: urutan yang baik bisa selesai dalam satu atau dua putaran.
Sejarah dan kegunaan
Alfonso Shimbel menjelaskan metode ini pada 1955, Lester Ford Jr. pada 1956, Edward F. Moore pada 1957, dan Richard Bellman pada 1958; nama algoritma ini diambil dari dua di antaranya, Bellman dan Ford. Putarannya bisa dijalankan oleh setiap router secara mandiri, sehingga menjadi dasar protokol routing distance-vector seperti RIP. Dalam keuangan, mengambil logaritma negatif dari kurs mengubah satu putaran perdagangan mata uang yang menguntungkan (arbitrase) menjadi siklus negatif, yang bisa ditemukan Bellman–Ford.
Jelajahi
Buka aplikasinya dan tekan Langkah. Setiap sisi satu arah, dan beberapa panjangnya negatif. Setiap langkah memeriksa satu sisi, dalam urutan tetap, dan ubin menunjukkan putaran serta berapa jarak yang diubahnya. Biasanya segera ada putaran yang tidak mengubah apa pun dan pencarian berhenti lebih awal. Centang Tambahkan siklus negatif dan lihat jarak turun putaran demi putaran sampai putaran pemeriksaan menemukan siklusnya dan menggambarnya merah.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu Bellman–Ford?
O(V · E) untuk V simpul dan E sisi: paling banyak V − 1 putaran, masing-masing memeriksa setiap sisi. Dengan berhenti lebih awal, dalam praktik sering jauh lebih cepat, dan dalam kasus terbaik satu putaran sudah cukup.
Apa itu siklus negatif?
Siklus yang panjang sisinya berjumlah kurang dari nol. Berputar di sana berulang kali membuat jalur sependek yang Anda mau, jadi jarak terpendek ke setiap simpul yang bisa dicapai lewat siklus itu tidak terdefinisi.
Apakah Bellman–Ford bisa dipakai pada graf tak berarah?
Hanya jika tidak ada sisi negatif: sisi negatif tak berarah bisa dilintasi bolak-balik, dan itu sudah merupakan siklus negatif dengan dua sisi. Dengan sisi tak negatif algoritma ini bisa dipakai, tetapi algoritma Dijkstra lebih cepat.
Apa itu SPFA?
Shortest Path Faster Algorithm, versi Bellman–Ford yang hanya memeriksa ulang sisi yang keluar dari simpul yang jaraknya baru berubah, dengan memakai antrean. Algoritma ini sering jauh lebih cepat, meski kasus terburuknya sama.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba Bellman–Ford