Apakah saya benar tentang perbedaan antara algoritma Floyd-Warshall, Dijkstra dan Bellman-Ford?

16

Saya telah mempelajari ketiganya dan saya menyatakan kesimpulan saya dari mereka di bawah ini. Bisakah seseorang memberi tahu saya jika saya sudah memahaminya dengan cukup akurat atau tidak? Terima kasih.

  1. Algoritma Dijkstra hanya digunakan ketika Anda memiliki satu sumber dan Anda ingin tahu jalur terkecil dari satu node ke yang lain, tetapi gagal dalam kasus-kasus seperti ini .

  2. Algoritma Floyd-Warshall digunakan ketika salah satu dari semua node dapat menjadi sumber, sehingga Anda ingin jarak terpendek untuk mencapai titik tujuan dari titik sumber mana pun. Ini hanya gagal ketika ada siklus negatif.

  3. Bellman-Ford digunakan seperti Dijkstra, ketika hanya ada satu sumber. Ini dapat menangani bobot negatif dan kerjanya sama dengan Floyd-Warshall kecuali untuk satu sumber, bukan? (Ini yang paling tidak aku yakini.)

Raphael
sumber
Selamat datang! Saya mengedit bagian kode yang berlebihan; orang dapat mengklik Wikipedia sendiri, atau memeriksa algoritme di buku teks favorit mereka. Perhatikan bahwa pertanyaan Anda aneh untuk ditanyakan, karena jawaban "ya" dapat terdiri dari tidak lebih.
Raphael

Jawaban:

23

Algoritma Dijkstra hanya digunakan ketika Anda memiliki satu sumber dan Anda ingin tahu jalur terkecil dari satu node ke yang lain, tetapi gagal [dalam grafik dengan tepi negatif]

Algoritma Dijkstra adalah salah satu contoh jalur terpendek sumber tunggal atau algoritma SSSP . Setiap algoritma SSSP menghitung jarak terpendek-jalan dari node sumber yang dipilih untuk setiap node yang lain dalam grafik. Selain itu, ia menghitung representasi kompak dari semua jalur terpendek dari s ke setiap simpul lainnya, dalam bentuk pohon yang di-root. Dalam kode Wikipedia, adalah induk dari v di pohon ini.ssprevious[v]v

Perilaku algoritma Dijkstra dalam grafik dengan tepi negatif tergantung pada varian tepat yang dibahas. Beberapa varian algoritme, seperti yang ada di Wikipedia, selalu berjalan cepat tetapi tidak menghitung jalur terpendek dengan benar ketika ada tepi negatif. Varian lain, seperti yang ada dalam catatan kuliah ini selalu menghitung jalur terpendek dengan benar (kecuali jika ada siklus negatif yang dapat dijangkau dari sumber) tetapi mungkin memerlukan waktu eksponensial dalam kasus terburuk jika ada tepi negatif.

Algoritma Floyd-Warshall digunakan ketika salah satu dari semua node dapat menjadi sumber, sehingga Anda ingin jarak terpendek untuk mencapai simpul tujuan dari simpul sumber mana pun. Ini hanya gagal ketika ada siklus negatif.

Itu benar. Floyd-Warshall adalah salah satu contoh dari algoritma jalur terpendek semua-pasangan , yang berarti ia menghitung jalur terpendek antara setiap pasangan node. Contoh lain adalah "untuk setiap simpul v, jalankan Dijkstra dengan v sebagai simpul sumber". Ada beberapa yang lain.

Bellman-Ford digunakan seperti Dijkstra, ketika hanya ada satu sumber. Ini dapat menangani bobot negatif dan kerjanya sama dengan Floyd-Warshall kecuali untuk satu sumber, bukan?

HAI(V3)HAI(V2E)HAI(VE)

Untuk perincian lebih lanjut, bacalah buku teks algoritma favorit Anda. (Anda memiliki buku teks algoritma favorit, bukan?)

JeffE
sumber
maukah Anda berbagi buku teks algoritma favorit Anda?
Abdul
2
@Abdul algorithmms.wtf
JeffE
@Abdul diberi umpan. - Buku teks yang digunakan di MIT / Stanford adalah T. Cormen, et al. Pengantar Algoritma. Buku teks yang digunakan di Cornell adalah J. Kleinberg, et al Algorithm Design. cs.sjtu.edu.cn/~jiangli/teaching/CS222/files/materials/…
AffluentOwl
2

Ketiga algoritma dibahas dalam slide kuliah oleh Prof. Jaehyun Park (Stanford University). Berikut ini tautan Algoritma Jalur Terpendek

Jitendra
sumber
Ini tidak menjawab pertanyaan tentang perbedaan dan tidak mandiri, hanya tautan tanpa ringkasan tidak dihitung sebagai jawaban yang baik. Juga tampaknya berlebihan, karena tidak mencakup lebih dari jawaban yang ada.
Evil
1

The Wikipedia halaman di masalah jalan terpendek menjelaskan dua masalah yang berbeda: SSSP dan APSP.

Jalur terpendek satu sumber (SSSP):

  • Algoritma Dijkstra: memecahkan masalah jalur terpendek satu sumber.
    • Batasan: Hanya tepi negatif yang tidak dapat ditanganinya.
    • Grafik tak tertimbang: Dijkstra's sama dengan BFS.
  • Algoritma Bellman – Ford: memecahkan masalah sumber tunggal jika bobot tepi mungkin negatif. Ini adalah peningkatan pada Dijkstra di mana ia sekarang dapat menangani bobot negatif juga.

Semua pasangan jalur terpendek (APSP):

  • Algoritma Floyd-Warshall: memecahkan semua pasangan jalur terpendek. Menangani tepi positif dan negatif.
    • Kendala: Tidak dapat menangani siklus negatif.

Oleh karena itu, Floyd-Warshall tidak sama dengan BFS, meskipun metodologi dasarnya sama, pemrograman dinamis.

Fooo
sumber
1

Mungkin ini harus berupa komentar daripada jawaban, tetapi merupakan perbedaan antara algoritma yang tidak disebutkan oleh jawaban lain.

Orang cenderung menyebut algoritma Floyd Floyd-Warshall , tetapi Floyd dan Warshall tidak sama.

Makalah Warshall mengamati bahwa jika Anda menggunakan algoritma Floyd pada matriks kejadian biner, yang Anda lakukan adalah perkalian matriks; karenanya, itu sebenarnya dapat diimplementasikan dengan cara itu, dan misalnya jika Anda dapat melakukan penggandaan vektor diHAI(1), algoritma Anda menjadi HAI(n2).

reinierpost
sumber