Putaran
Berubah di putaran ini
Sisi diperiksa

  • Saat ini
  • Sudah berjarak
  • Sisi terpakai
  • Jalur
  • Siklus negatif
Klik pada simpul mengatur

Selengkapnya tentang algoritma Bellman–Ford

Algoritma Bellman–Ford

Algoritma Dijkstra gagal jika ada sisi dengan panjang negatif, seperti jalan yang membayar Anda alih-alih menarik tol. Algoritma Bellman–Ford tidak: ia hanya memeriksa setiap sisi berulang kali sampai tidak ada yang membaik, dan bahkan bisa tahu jika sebuah siklus membuat jarak turun terus-menerus. Klik simpul untuk mulai dari sana dan jalankan putaran demi putaran. Tekan Putar untuk melihat pencarian, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Setiap sisi satu arah, seperti ditunjukkan panahnya, dan angka di atasnya adalah panjangnya, yang bisa negatif. Klik simpul untuk menjadikannya awal; ubah klik ke Tujuan lalu klik simpul lain untuk melihat jalur terpendek ke sana di akhir. Angka di tiap simpul adalah jaraknya sejauh ini. Centang Tambahkan siklus negatif untuk melihat cara Bellman–Ford menemukannya. Graf baru membuat graf lain; pilih berapa simpul dan sisinya. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Klik simpul untuk menjadikannya awal. Untuk melihat jalur di akhir, ubah klik ke Tujuan lalu klik simpul lain.
  2. Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja.
  3. Centang Tambahkan siklus negatif untuk melihat Bellman–Ford menemukannya. Graf baru membuat graf lain untuk dicoba.

Cara kerja Bellman–Ford

Beri simpul awal jarak 0 dan semua simpul lain tak hingga. Lalu jalankan putaran: di setiap putaran, periksa setiap sisi u → v sekali. Jika u punya jarak dan dist(u) ditambah panjang sisi lebih pendek dari dist(v), turunkan dist(v) dan ingat u sebagai jalan ke sana. Setelah putaran k, setiap jalur terpendek yang memakai paling banyak k sisi sudah diketahui. Jalur terpendek mengunjungi tiap simpul paling banyak sekali, jadi punya paling banyak n − 1 sisi, dan n − 1 putaran selalu cukup. Jika satu putaran penuh tidak mengubah apa pun, pencarian bisa berhenti lebih awal.

Menemukan siklus negatif

Jika sisi-sisi sebuah siklus berjumlah kurang dari nol, berputar sekali lagi selalu membuat jalur lebih pendek, jadi tidak ada jalur terpendek sama sekali. Bellman–Ford menyadarinya: setelah n − 1 putaran, satu putaran lagi seharusnya tidak mengubah apa pun. Jika masih ada sisi yang bisa direlaksasi, ada siklus negatif yang bisa dicapai dari awal, dan mengikuti simpul yang diingat mundur dari sisi itu akan masuk ke siklus tersebut. Di aplikasi, siklus itu digambar merah.

Pertanyaan yang sering diajukan

Apa itu algoritma Bellman–Ford?

Algoritma yang menemukan jalur terpendek dari satu simpul awal ke setiap simpul lain pada graf yang sisinya boleh punya panjang negatif. Algoritma ini merelaksasi setiap sisi dalam putaran berulang, dan melaporkan siklus negatif jika ada yang bisa dicapai dari awal.

Mengapa algoritma Dijkstra gagal dengan sisi negatif?

Dijkstra membuat jarak simpul final begitu simpul itu menjadi yang terdekat dalam antrean. Sisi negatif yang ditemukan kemudian masih bisa membawa kembali ke simpul itu lewat jalan yang lebih pendek, jadi jarak finalnya bisa salah. Bellman–Ford tidak pernah membuat jarak final terlalu dini; ia terus memeriksa setiap sisi.

Mengapa n − 1 putaran?

Jalur terpendek tidak pernah perlu mengunjungi simpul dua kali, jadi punya paling banyak n − 1 sisi. Setiap putaran memperpanjang jalur terpendek yang diketahui setidaknya satu sisi, jadi setelah n − 1 putaran semuanya ditemukan.

Seberapa cepat Bellman–Ford?

Setiap putaran memeriksa semua E sisi dan ada paling banyak V − 1 putaran, jadi kerjanya tumbuh sebanding V × E. Itu lebih lambat dari algoritma Dijkstra, sebabnya Bellman–Ford dipakai saat sisi bisa negatif.

Apakah graf saya dikirim ke mana pun?

Tidak. Graf dibuat dan dicari di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor