Mengapa DFS tidak dapat digunakan untuk menemukan jalur terpendek dalam grafik tidak tertimbang?

Saya mengerti bahwa menggunakan DFS "sebagaimana adanya" tidak akan menemukan jalur terpendek dalam grafik tidak tertimbang.

Tetapi mengapa mengutak-atik DFS untuk memungkinkannya menemukan jalur terpendek dalam grafik tak tertimbang sedemikian rupa sehingga menjadi harapan yang sia-sia? Semua teks pada subjek hanya menyatakan bahwa itu tidak dapat dilakukan. Saya tidak yakin (tanpa mencobanya sendiri).

Apakah Anda tahu modifikasi apa pun yang akan memungkinkan DFS menemukan jalur terpendek dalam grafik tidak tertimbang? Jika tidak, ada apa dengan algoritma yang membuatnya sangat sulit?

Satu-satunya elemen pencarian mendalam-pertama yang Anda ubah adalah urutan penyelidikan anak-anak. Versi normal berlangsung dalam urutan acak, yaitu dalam urutan anak-anak disimpan.

Satu-satunya alternatif yang layak (menuju jalur terpendek) yang bisa saya temukan adalah pendekatan serakah, yaitu melihat anak-anak dalam urutan jarak mereka dari simpul saat ini (dari kecil ke besar). Sangat mudah untuk membuat sampel tandingan untuk aturan ini:

^{[ sumber ]}

Sekarang, itu bukan bukti bahwa tidak ada strategi untuk memilih anak berikutnya yang akan diselidiki yang akan membuat DFS menemukan jalur terpendek.

Namun, tidak peduli aturan¹ Anda dapat membuat grafik yang memiliki DFS berkomitmen untuk jalan memutar panjang pada simpul pertama, seperti yang saya lakukan untuk aturan serakah. Tetapkan tepi dan bobot sedemikian sehingga aturan memilih untuk mengunjungi pertama, dan menetapkan bobot yang lebih besar daripada yang . Oleh karena itu, masuk akal bahwa DFS tidak pernah dapat menemukan jalur terpendek (dalam grafik umum).( s , a ) a ( a , b ) ( s , t $(s,t)$$(s,a)$$a$$(a,b)$$(s,t)$

Perhatikan bahwa karena Anda dapat mengekspresikan setiap grafik berbobot (bilangan positif-bilangan bulat) sebagai grafik tidak berbobot - cukup ganti tepi dengan biaya dengan rantai dengan simpul - contoh yang sama berhubungan dengan DFS pada grafik tanpa bobot. Di sini, situasinya bahkan lebih suram: tanpa beban, apa yang bisa digunakan DFS untuk menentukan anak berikutnya yang akan dikunjungi?c - $c$$c-1$

1. Selama aturannya deterministik. Jika tidak, itu jelas tidak selalu dapat menemukan jalur terpendek.

Breadth -first-search adalah algoritma yang akan menemukan jalur terpendek dalam grafik tidak tertimbang.

Ada tweak sederhana untuk mendapatkan dari DFS ke sebuah algoritma yang akan menemukan jalur terpendek pada grafik tidak tertimbang. Pada dasarnya, Anda mengganti tumpukan yang digunakan oleh DFS dengan antrian. Namun, algoritma yang dihasilkan tidak lagi disebut DFS. Sebagai gantinya, Anda akan menerapkan pencarian luas pertama.

Paragraf di atas memberikan intuisi yang benar, tetapi terlalu menyederhanakan situasi sedikit. Sangat mudah untuk menulis kode yang swap sederhana tidak memberikan implementasi pencarian pertama yang luas, tetapi juga mudah untuk menulis kode yang pada awalnya terlihat seperti implementasi yang benar tetapi sebenarnya tidak. Anda dapat menemukan pertanyaan cs.SE terkait BFS vs DFS di sini . Anda dapat menemukan beberapa kode pseudo yang bagus di sini.

Kamu bisa!!!

Tandai node sebagai dikunjungi saat Anda pergi mendalam dan menghapus tanda saat Anda kembali, saat kembali ketika Anda menemukan cabang lain ulangi sama.

Hemat biaya / jalur untuk semua kemungkinan pencarian di mana Anda menemukan node target, bandingkan semua biaya / jalur tersebut dan pilih yang terpendek.

Masalah besar (dan saya maksudkan BESAR) dengan pendekatan ini adalah bahwa Anda akan mengunjungi simpul yang sama beberapa kali yang membuat dfs pilihan yang jelas buruk untuk algoritma jalur terpendek.

BFS memiliki properti yang bagus yang akan memeriksa semua tepi dari root dan menjaga jarak dari root ke node lain seminimal mungkin, tetapi dfs hanya melompat ke node yang berdekatan pertama dan berjalan dengan bijak. Anda BISA memodifikasi DFS untuk mendapatkan jalur terpendek, tetapi Anda hanya akan berakhir dalam algoritme yang memiliki kompleksitas waktu lebih tinggi atau pada akhirnya akan melakukan hal yang sama seperti yang dilakukan BFS

TI dimungkinkan untuk menemukan jalur antara dua simpul dengan jumlah tepi minimum menggunakan DFS. kita bisa menerapkan pendekatan level

Kamu bisa

cukup lintasi grafik dengan cara dfs dan periksa

if(distance[dest] > distance[source]+cost[source_to_destination]){
    distance[dest] = distance[source] + cost[source_to_destination]);
}

Inilah tautan untuk solusi lengkap