Saya mengimplementasikan solusi algoritma Bellman - Ford dengan antrian dan saya membandingkan kinerjanya dengan algoritma Dijkstra. Mereka cukup dekat dan itu merupakan kejutan bagi saya karena kompleksitas Bellman - Ford adalah O(NM). Saya tahu kerumitannya adalah untuk kasus terburuk, namun hasilnya tetap mengejutkan. Saya mencari beberapa informasi tentang Bellman - Ford dan saya hanya menemukan pernyataan ini di Sedgewick, Algoritma di Java "pada jaringan nyata, algoritma Bellman – Ford biasanya berjalan dalam waktu linier". Bisakah Anda memberi saya penjelasan tentang perilaku kinerja algoritma Bellman - Ford?
Kinerja algoritma jalur terpendek Bellman – Ford
comment
Jika Anda mencari implementasi yang baik dari kedua algoritma di c++, lihat meningkatkan lib grafik. boost.org/doc/libs/1_39_0/libs/ grafik/doc/table_of_contents.html
- person RED SOFT ADAIR schedule 16.06.2009
comment
Kode ada di sini: github.com/boostorg/graph/ gumpalan/kembangkan/sertakan/boost/graph/
- person assylias schedule 24.08.2018
Jawaban (1)
Berikut adalah makalah yang cukup jelas (Tautan PDF).
Kompleksitas algoritma Bellman-Ford bergantung pada jumlah pemeriksaan tepi, atau panggilan relaksasi. (Perhatikan bahwa ini berbeda dengan langkah relaksasi yang mengacu pada perubahan aktual yang dilakukan.) Seperti disebutkan, jumlah panggilan relaksasi bisa lebih kecil dari |V ||E| dengan implementasi BGL. Faktanya, ini jauh lebih kecil dari |V ||E| dalam kasus rata-rata.
Ini mencantumkan kodesemu dan analisis lebih lanjut juga.
person
JP Alioto
schedule
15.06.2009
