Mengapa menggunakan Algoritma Dijkstra jika Breadth First Search (BFS) dapat melakukan hal yang sama dengan lebih cepat?

110

Keduanya dapat digunakan untuk menemukan jalur terpendek dari satu sumber. BFS masuk O(E+V), sementara Dijkstra masuk O((V+E)*log(V)).

Juga, saya telah melihat Dijkstra banyak digunakan seperti dalam protokol routing.

Jadi, mengapa menggunakan algoritma Dijkstra jika BFS dapat melakukan hal yang sama dengan lebih cepat?

algorithm graph dijkstra breadth-first-search kucing jahe
sumber

Jawaban:

156

Dijkstra memungkinkan menetapkan jarak selain 1 untuk setiap langkah. Misalnya, dalam merutekan jarak (atau bobot) dapat ditentukan oleh kecepatan, biaya, preferensi, dll. Algoritme tersebut kemudian memberi Anda jalur terpendek dari sumber Anda ke setiap node dalam grafik yang dilintasi.

Sementara itu BFS pada dasarnya hanya memperluas pencarian dengan satu "langkah" (link, edge, apa pun yang Anda ingin menyebutnya dalam aplikasi Anda) pada setiap iterasi, yang kebetulan memiliki efek menemukan jumlah langkah terkecil yang diperlukan untuk mencapai setiap node yang diberikan dari sumber Anda ("root").

Arkku
sumber
1
Keduanya akan menghasilkan hasil yang sama yaitu jalur antara dua simpul, tetapi hanya dijkstra yang akan menjamin jalur terpendek.
Edwin
Lihat jawaban yang diterima, komentar kedua. Cara yang sangat bagus untuk menjelaskan mengapa kompleksitas komputasi berbeda: stackoverflow.com/questions/25449781/…
jmcarter9t
24

Jika Anda mempertimbangkan situs web perjalanan, ini menggunakan algoritma Dijkstra karena bobot (jarak) pada node.

Jika Anda akan mempertimbangkan jarak yang sama antara semua node, maka BFS adalah pilihan yang lebih baik.

Misalnya, pertimbangkan A -> (B, C) -> (F)dengan bobot tepi yang diberikan oleh A->B= 10, A->C= 20, B->F= C->F= 5.

Di sini, jika kita menerapkan BFS, jawabannya adalah ABF atau ACF, karena keduanya adalah jalur terpendek (sehubungan dengan jumlah sisi), tetapi jika kita menerapkan Dijstra, jawabannya adalah ABF hanya karena mempertimbangkan bobot pada yang terhubung jalan.

Saurabh Saluja
sumber
4

Dari perspektif implementasi, algoritma Dijkstra dapat diimplementasikan persis seperti BFS dengan menukar queuedengan apriority queue .

Sumber

havij
sumber