Bellman-Ford dan Sisi Negatif
Kendalikan nilai negatif dan kesan kitaran.
Bellman-Ford dan Sisi Negatif ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apabila Dijkstra Gagal
Dijkstra menganggap jarak yang dikeluarkan sudah muktamad, tetapi sisi negatif boleh menyebabkan laluan menjadi lebih murah kemudian. Sebab itulah algoritma ini gagal.
Perkenalkan Bellman-Ford
Bellman-Ford mengendalikan berat sisi negatif. Algoritma ini lebih perlahan daripada Dijkstra, tetapi teguh apabila logik tamak tidak boleh dipercayai.
Operasi Teras
Algoritma ini berulang kali melonggarkan setiap sisi: jika dist[u] ditambah berat sisi lebih kecil daripada dist[v], kemas kini dist[v] kepada nilai yang lebih kecil itu.
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wBerapa Banyak Pusingan
Laluan terpendek menggunakan paling banyak V - 1 sisi, jadi V-1 pusingan untuk melonggarkan setiap sisi sudah mencukupi bagi menetapkan semua jarak.
for _ in range(n - 1):
relax_all_edges()Mulakan Jarak
Mulakan dengan setiap jarak pada infiniti, kecuali sumber yang ditetapkan kepada sifar, sama seperti dalam Dijkstra.
dist = [float('inf')] * n
dist[src] = 0Satu Pusingan Penuh
Setiap pusingan melintasi keseluruhan senarai sisi sekali dan melonggarkan setiap sisi. Penambahbaikan merebak keluar sejauh satu sambungan pada setiap pusingan.
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wMengapa V-1 Mencukupi
Selepas k pusingan, semua laluan terpendek yang menggunakan k sisi adalah betul. Selepas V-1 pusingan, setiap laluan terpendek mudah telah selesai.
Pusingan Tambahan
Jalankan satu pusingan lagi. Jika mana-mana jarak masih berkurang, kos terus menjadi lebih murah, yang menandakan adanya kitaran negatif.
Mengesan Kitaran Negatif
Kitaran negatif bermaksud tiada laluan terpendek terhingga wujud, kerana Anda boleh mengulanginya tanpa henti untuk mengurangkan kos tanpa had.
for u, v, w in edges:
if dist[u] + w < dist[v]:
return 'negative cycle'Masa Pelaksanaan
Anda melonggarkan E sisi merentasi V pusingan, jadi Bellman-Ford berjalan dalam O(V * E), sesuai untuk graf kecil atau sederhana.
Dijkstra atau Bellman-Ford
Pilih Dijkstra untuk berat tidak negatif dan kelajuan. Pilih Bellman-Ford apabila wujud berat negatif atau Anda mesti mengesan kitaran yang bermasalah.
Semakan Pantas
Selepas V-1 pusingan, jarak masih berkurang pada satu pusingan tambahan. Apakah maksudnya?
Imbas Kembali: Bellman-Ford
Longgarkan semua sisi selama V-1 pusingan, kemudian lakukan satu pusingan lagi untuk mengesan kitaran negatif. Algoritma ini ialah O(V*E), tetapi berfungsi apabila Dijkstra tidak boleh digunakan. ✅
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Bellman-Ford dan Sisi Negatif” percuma?
Ya — teks penuh “Bellman-Ford dan Sisi Negatif” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Bellman-Ford dan Sisi Negatif”?
Kendalikan nilai negatif dan kesan kitaran. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.
Berapa lamakah pelajaran “Bellman-Ford dan Sisi Negatif” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Dijkstra dengan Timbunan
- 0-1 BFS dengan Deque
- Bellman-Ford dan Sisi Negatif
- Floyd-Warshall Semua Pasangan