Saya telah melakukan beberapa penelitian, dan sepertinya saya kehilangan satu bagian kecil dari algoritma ini. Saya mengerti bagaimana Pencarian Lebar-Pertama bekerja, tapi saya tidak mengerti bagaimana persisnya itu akan membawa saya ke jalur tertentu, dibandingkan dengan hanya memberitahu saya di mana setiap node individu dapat pergi. Saya kira cara termudah untuk menjelaskan kebingungan saya adalah dengan memberikan contoh:
Jadi misalnya, katakanlah saya memiliki grafik seperti ini:
Dan tujuan saya adalah beralih dari A ke E (semua sisi tidak berbobot).
Saya mulai dari A, karena itulah asal saya. Saya mengantri A, diikuti dengan segera mengeluarkan A dan menjelajahinya. Ini menghasilkan B dan D, karena A terhubung ke B dan D. Saya dengan demikian mengantri B dan D.
Saya dequeue B dan menjelajahinya, dan menemukan bahwa itu mengarah ke A (sudah dieksplorasi), dan C, jadi saya mengantri C. Saya kemudian dequeue D, dan menemukan bahwa itu mengarah ke E, tujuan saya. Saya kemudian dequeue C, dan menemukan bahwa itu juga mengarah ke E, tujuan saya.
Saya tahu secara logis bahwa jalur tercepat adalah A-> D-> E, tetapi saya tidak yakin bagaimana tepatnya pencarian pertama kali membantu - bagaimana saya harus merekam jalur sehingga ketika saya selesai, saya dapat menganalisis hasilnya dan melihat bahwa jalur terpendek adalah A-> D-> E?
Juga, perhatikan bahwa saya sebenarnya tidak menggunakan pohon, jadi tidak ada simpul "induk", hanya anak-anak.
Jawaban:
Secara teknis, pencarian Breadth-first (BFS) dengan sendirinya tidak memungkinkan Anda menemukan jalur terpendek, hanya karena BFS tidak mencari jalur terpendek: BFS menggambarkan strategi untuk mencari grafik, tetapi tidak mengatakan bahwa Anda harus mencari apapun khususnya.
Algoritma Dijkstra mengadaptasi BFS untuk memungkinkan Anda menemukan jalur terpendek satu sumber.
Untuk mengambil jalur terpendek dari titik asal ke sebuah simpul, Anda perlu mempertahankan dua item untuk setiap simpul dalam grafik: jarak terpendeknya saat ini, dan simpul sebelumnya di jalur terpendek. Awalnya semua jarak diatur hingga tak terbatas, dan semua pendahulu diatur ke kosong. Dalam contoh Anda, Anda menetapkan jarak A ke nol, dan kemudian melanjutkan dengan BFS. Pada setiap langkah Anda memeriksa apakah Anda dapat meningkatkan jarak turunan, yaitu jarak dari titik asal ke pendahulunya ditambah panjang tepi yang Anda jelajahi kurang dari jarak terbaik saat ini untuk simpul yang dimaksud. Jika Anda dapat meningkatkan jarak, atur jalur terpendek baru, dan ingat pendahulunya melalui jalur mana yang telah diperoleh. Ketika antrian BFS kosong, pilih sebuah node (dalam contoh Anda, itu E) dan lintasi pendahulunya kembali ke asal.
Jika ini terdengar agak membingungkan, wikipedia memiliki bagian kode pseudocode yang bagus tentang topik ini.
sumber
Seperti yang ditunjukkan di atas, BFS hanya dapat digunakan untuk menemukan jalur terpendek dalam grafik jika:
Tidak ada loop
Semua tepi memiliki bobot yang sama atau tidak sama berat.
Untuk menemukan jalur terpendek, yang harus Anda lakukan adalah mulai dari sumber dan melakukan pencarian pertama yang luas dan berhenti ketika Anda menemukan Node tujuan Anda. Satu-satunya hal tambahan yang perlu Anda lakukan adalah memiliki array sebelumnya [n] yang akan menyimpan node sebelumnya untuk setiap node yang dikunjungi. Sumber sebelumnya bisa nol.
Untuk mencetak path, loop sederhana melalui array [] sebelumnya dari sumber hingga Anda mencapai tujuan dan mencetak node. DFS juga dapat digunakan untuk menemukan jalur terpendek dalam grafik di bawah kondisi yang sama.
Namun, jika grafiknya lebih kompleks, mengandung tepi dan loop berbobot, maka kita memerlukan versi BFS yang lebih canggih, yaitu algoritma Dijkstra.
sumber
To print the path, simple loop through the previous[] array from source till you reach destination.
Tetapi sumber sebelumnya adalah nol. Saya pikir yang Anda maksud adalahbacktrace from destination using the previous array until you reach the source
,.Dari tutorial di sini
sumber
Saya telah menghabiskan 3 hari
akhirnya memecahkan pertanyaan grafik yang
digunakan untuk
menemukan jarak terpendek
menggunakan BFS
Ingin berbagi pengalaman.
Saya telah kehilangan 3 hari mencoba semua alternatif di atas, memverifikasi & memverifikasi ulang lagi dan lagi di atas
mereka bukan masalah.
(Cobalah untuk menghabiskan waktu mencari masalah lain, jika Anda tidak menemukan masalah dengan di atas 5).
Penjelasan lebih lanjut dari komentar di bawah ini:
Asumsikan di atas adalah grafik
grafik Anda turun ke bawah
Untuk A, adjacents adalah B & C
Untuk B, adjacents adalah D & E
Untuk C, adjacents adalah F & G
katakanlah, mulai simpul adalah A
ketika Anda mencapai A, ke, B & C jarak terdekat ke B & C dari A adalah 1
ketika Anda mencapai D atau E, melalui B, jarak terdekat ke A & D adalah 2 (A-> B-> D)
sama, A-> E adalah 2 (A-> B-> E)
juga, A-> F & A-> G adalah 2
Jadi, sekarang alih-alih 1 jarak antar node, jika 6, maka gandakan jawabannya dengan 6
contoh,
jika jarak antara masing-masing adalah 1, maka A-> E adalah 2 (A-> B-> E = 1 + 1 )
jika jarak antara masing-masing adalah 6, maka A-> E adalah 12 (A-> B-> E = 6 + 6)
ya, bfs dapat mengambil jalur apa pun
tetapi kami menghitung untuk semua jalur
jika Anda harus beralih dari A ke Z, maka kami menempuh semua jalur dari A ke perantara I, dan karena akan ada banyak jalur, kami membuang semua kecuali jalur terpendek hingga saya, lalu melanjutkan dengan jalur terpendek ke depan ke simpul J
lagi jika ada beberapa jalur dari I ke J, kita hanya mengambil satu
contoh terpendek ,
asumsikan,
A -> I kita memiliki jarak 5
(LANGKAH) berasumsi, I -> J kita memiliki banyak jalur, dari jarak 7 & 8, karena 7 adalah yang terpendek
kita ambil A -> J sebagai 5 (A-> I terpendek) + 8 (terpendek sekarang) = 13
jadi A-> J sekarang 13
kita ulangi sekarang di atas (LANGKAH) untuk J -> K dan seterusnya, sampai kita dapatkan ke Z
Baca bagian ini, 2 atau 3 kali, dan menggambar di atas kertas, Anda pasti akan mendapatkan apa yang saya katakan, semoga beruntung
sumber
Berdasarkan jawaban acheron55 saya memposting implementasi yang mungkin di sini .
Berikut ini ringkasan singkatnya:
Yang harus Anda lakukan adalah melacak jalur yang dilaluinya target telah tercapai. Cara sederhana untuk melakukannya, adalah mendorong ke
Queue
seluruh jalur yang digunakan untuk mencapai suatu simpul, bukan dari simpul itu sendiri.Manfaat melakukannya adalah ketika target telah tercapai, antrian memegang jalur yang digunakan untuk mencapainya.
Ini juga berlaku untuk grafik siklik, di mana simpul dapat memiliki lebih dari satu orangtua.
sumber
Mengunjungi utas ini setelah beberapa saat tidak aktif, tetapi mengingat bahwa saya tidak melihat jawaban yang menyeluruh, inilah dua sen saya.
Pencarian Breadth-first akan selalu menemukan jalur terpendek dalam grafik tanpa bobot. Grafik dapat berupa siklik atau asiklik.
Lihat di bawah untuk kodesemu. Kodesemu ini mengasumsikan bahwa Anda menggunakan antrian untuk mengimplementasikan BFS. Itu juga mengasumsikan Anda dapat menandai simpul sebagai dikunjungi, dan bahwa setiap simpul menyimpan parameter jarak, yang diinisialisasi hingga tak terbatas.
Perhatikan bahwa pendekatan ini tidak berfungsi untuk grafik berbobot - untuk itu, lihat algoritma Dijkstra.
sumber
Solusi berikut ini berfungsi untuk semua kasus uji.
sumber