Adakah yang bisa memberi tahu saya mengapa algoritma Dijkstra untuk jalur terpendek sumber tunggal mengasumsikan bahwa tepinya harus non-negatif.
Saya berbicara tentang sisi saja bukan siklus bobot negatif.
Adakah yang bisa memberi tahu saya mengapa algoritma Dijkstra untuk jalur terpendek sumber tunggal mengasumsikan bahwa tepinya harus non-negatif.
Saya berbicara tentang sisi saja bukan siklus bobot negatif.
Jawaban:
Ingatlah bahwa dalam algoritme Dijkstra, setelah sebuah simpul ditandai sebagai "tertutup" (dan keluar dari set terbuka) - algoritme menemukan jalur terpendek ke sana , dan tidak perlu mengembangkan simpul ini lagi - ini mengasumsikan jalur yang dikembangkan ke sana jalur adalah yang terpendek.
Tetapi dengan bobot negatif - itu mungkin tidak benar. Sebagai contoh:
Dijkstra dari A pertama-tama akan mengembangkan C, dan kemudian gagal menemukannya
A->B->C
EDIT penjelasan yang lebih dalam:
Perhatikan bahwa ini penting, karena dalam setiap langkah relaksasi, algoritme mengasumsikan "biaya" ke node "tertutup" memang minimal, dan dengan demikian node yang akan dipilih selanjutnya juga minimal.
Idenya adalah: Jika kita memiliki simpul terbuka sehingga biayanya minimal - dengan menambahkan bilangan positif ke sembarang simpul - minimalitas tidak akan pernah berubah.
Tanpa batasan pada bilangan positif - asumsi di atas tidak benar.
Karena kita "tahu" setiap simpul yang "tertutup" adalah minimal - kita bisa melakukan langkah relaksasi dengan aman - tanpa "melihat ke belakang". Jika kita memang perlu "melihat ke belakang" - Bellman-Ford menawarkan solusi seperti rekursif (DP) untuk melakukannya.
sumber
A->B
akan 5 danA->C
akan 2. KemudianB->C
akan-5
. Jadi nilainyaC
akan-5
sama dengan bellman-ford. Bagaimana ini tidak memberikan jawaban yang benar?A
dengan nilai 0. Kemudian akan melihat node yang bernilai minimal,B
adalah 5 danC
2. Minimal adalahC
, sehingga akan menutupC
dengan nilai 2 dan tidak akan pernah melihat ke belakang, ketika nantiB
ditutup, tidak dapat mengubah nilaiC
, karena sudah "ditutup".A -> B -> C
? Ini pertama-tama akan memperbaruiC
jarak ke 2, dan kemudianB
jarak ke 5. Dengan asumsi bahwa dalam grafik Anda tidak ada tepi keluar dariC
, maka kami tidak melakukan apa-apa saat mengunjungiC
(dan jaraknya masih 2). Kemudian kita mengunjungiD
node yang berdekatan, dan satu-satunya node yang berdekatan adalahC
, yang jarak barunya -5. Perhatikan bahwa dalam algoritma Dijkstra, kita juga melacak induk dari mana kita menjangkau (dan memperbarui) simpul, dan melakukannyaC
, Anda akan mendapatkan indukB
, dan kemudianA
, menghasilkan hasil yang benar. Apa yang saya lewatkan?Pertimbangkan grafik yang ditunjukkan di bawah ini dengan sumber sebagai Vertex A. Pertama coba jalankan sendiri algoritma Dijkstra di atasnya.
Ketika saya mengacu pada algoritma Dijkstra dalam penjelasan saya, saya akan berbicara tentang Algoritma Dijkstra seperti yang diterapkan di bawah ini,
Jadi memulai nilai ( jarak dari sumber ke simpul ) yang awalnya ditetapkan untuk setiap simpul adalah,
Pertama-tama kita mengekstrak simpul di Q = [A, B, C] yang memiliki nilai terkecil, yaitu A, setelah itu Q = [B, C] . Catatan A memiliki tepi terarah ke B dan C, juga keduanya di Q, oleh karena itu kami memperbarui kedua nilai tersebut,
Sekarang kita mengekstrak C sebagai (2 <5), sekarang Q = [B] . Perhatikan bahwa C tidak terhubung ke apa-apa, jadi
line16
loop tidak berjalan.Akhirnya kami mengekstrak B, setelah itu . Catatan B memiliki tepi terarah ke C tetapi C tidak ada di Q oleh karena itu kami sekali lagi tidak memasukkan perulangan for
line16
,Jadi kami berakhir dengan jarak sebagai
Perhatikan bagaimana ini salah karena jarak terpendek dari A ke C adalah 5 + -10 = -5, saat Anda pergi .
Jadi untuk grafik ini Algoritma Dijkstra salah menghitung jarak dari A ke C.
Hal ini terjadi karena Algoritma Dijkstra tidak mencoba untuk menemukan jalan yang lebih pendek untuk simpul yang sudah diekstrak dari Q .
Apa yang dilakukan
line16
loop adalah mengambil simpul u dan berkata "hei sepertinya kita bisa pergi ke v dari sumber melalui u , apakah jarak (alt atau alternatif) lebih baik daripada dist [v] yang kita punya saat ini? Jika demikian, mari perbarui dist [v] "Perhatikan bahwa dalam
line16
mereka memeriksa semua tetangga v (yaitu tepi diarahkan ada dari u ke v ), dari u yang masih dalam Q . Diline14
dalamnya mereka menghapus catatan yang dikunjungi dari Q. Jadi jika x adalah tetangga yang dikunjungi dari u , jalur tersebut bahkan tidak dianggap sebagai cara yang mungkin lebih pendek dari sumber ke v .Dalam contoh kita di atas, C adalah tetangga yang dikunjungi dari B, sehingga jalur tersebut tidak dipertimbangkan, meninggalkan jalur terpendek saat ini tidak berubah.
Ini sebenarnya berguna jika bobot sisi semua bilangan positif , karena kita tidak akan membuang waktu kita mempertimbangkan jalur yang tidak bisa lebih pendek.
Jadi saya katakan bahwa ketika menjalankan algoritma ini jika x diekstrak dari Q sebelum y , maka tidak mungkin untuk menemukan jalur - yang lebih pendek. Izinkan saya menjelaskan ini dengan sebuah contoh,
Karena y baru saja diekstraksi dan x telah diekstraksi sebelum dirinya sendiri, maka dist [y]> dist [x] karena jika tidak y akan diekstraksi sebelum x . (
line 13
jarak min dulu)Dan seperti yang telah kita asumsikan bahwa bobot sisi positif, yaitu panjang (x, y)> 0 . Jadi jarak alternatif (alt) melalui y pasti selalu lebih besar, yaitu dist [y] + panjang (x, y)> dist [x] . Jadi nilai dist [x] tidak akan diperbarui meskipun y dianggap sebagai jalur ke x , jadi kami menyimpulkan bahwa masuk akal untuk hanya mempertimbangkan tetangga dari y yang masih di Q (catat komentar di
line16
)Tetapi hal ini bergantung pada asumsi kita tentang panjang tepi positif, jika panjang (u, v) <0 maka tergantung pada seberapa negatif tepi tersebut kita dapat mengganti dist [x] setelah perbandingan di
line18
.Karena masing-masing simpul v tersebut adalah simpul terakhir kedua pada jalur potensial yang "lebih baik" dari sumber ke x , yang dibuang oleh algoritma Dijkstra.
Jadi dalam contoh yang saya berikan di atas, kesalahannya adalah karena C telah dihapus sebelum B dihapus. Sedangkan C adalah tetangga B dengan sisi negatif!
Sekadar klarifikasi, B dan C adalah tetangga A. B memiliki satu tetangga C dan C tidak memiliki tetangga. panjang (a, b) adalah panjang tepi antara simpul a dan b.
sumber
Algoritma Dijkstra mengasumsikan jalur hanya bisa menjadi 'lebih berat', sehingga jika Anda memiliki jalur dari A ke B dengan bobot 3, dan jalur dari A ke C dengan bobot 3, tidak mungkin Anda dapat menambahkan tepi dan dapatkan dari A ke B melalui C dengan berat kurang dari 3.
Asumsi ini membuat algoritme lebih cepat daripada algoritme yang harus memperhitungkan bobot negatif.
sumber
Ketepatan algoritma Dijkstra:
Kami memiliki 2 set simpul di setiap langkah algoritma. Set A terdiri dari simpul yang telah kita hitung jalur terpendeknya. Set B terdiri dari simpul-simpul yang tersisa.
Hipotesis Induktif : Pada setiap langkah kami akan mengasumsikan bahwa semua iterasi sebelumnya benar.
Langkah Induktif : Ketika kita menambahkan titik V ke himpunan A dan mengatur jarak menjadi dist [V], kita harus membuktikan bahwa jarak ini optimal. Jika ini tidak optimal maka harus ada jalur lain ke simpul V yang panjangnya lebih pendek.
Misalkan ini beberapa jalan lain melewati beberapa titik X.
Sekarang, karena dist [V] <= dist [X], oleh karena itu setiap jalur lain ke V akan memiliki panjang paling sedikit dist [V], kecuali grafik tersebut memiliki panjang sisi negatif.
Jadi agar algoritme dijkstra berfungsi, bobot tepi harus bukan negatif.
sumber
Coba algoritma Dijkstra pada grafik berikut, dengan asumsi
A
node sumber, untuk melihat apa yang terjadi:sumber
A->B
akan1
danA->C
akan100
. LaluB->D
akan2
. LaluC->D
akan-4900
. Jadi nilainyaD
akan-4900
sama dengan bellman-ford. Bagaimana ini tidak memberikan jawaban yang benar?A->B
akan1
danA->C
akan menjadi100
. KemudianB
dieksplorasi dan diaturB->D
ke2
. Lalu D dieksplorasi karena saat ini ia memiliki jalur terpendek kembali ke sumbernya? Apakah saya benar mengatakan bahwa jikaB->D
dulu100
,C
akankah dieksplorasi terlebih dahulu? Saya memahami semua contoh lain yang diberikan orang kecuali Anda.Ingatlah bahwa dalam algoritma Dijkstra, setelah sebuah simpul ditandai sebagai "tertutup" (dan keluar dari set terbuka) - ini mengasumsikan bahwa setiap simpul yang berasal darinya akan mengarah ke jarak yang lebih jauh sehingga, algoritma menemukan jalur terpendek ke sana, dan akan tidak perlu mengembangkan simpul ini lagi, tetapi ini tidak berlaku jika ada bobot negatif.
sumber
Jawaban lain sejauh ini menunjukkan dengan cukup baik mengapa algoritma Dijkstra tidak dapat menangani bobot negatif di jalur.
Tetapi pertanyaan itu sendiri mungkin didasarkan pada pemahaman yang salah tentang bobot jalur. Jika bobot negatif pada jalur diizinkan dalam algoritme pencarian jalur secara umum, Anda akan mendapatkan loop permanen yang tidak akan berhenti.
Pertimbangkan ini:
Apa jalur optimal antara A dan D?
Algoritma pencarian jalan harus terus menerus mengulang antara B dan C karena hal itu akan mengurangi bobot dari jalur total. Jadi mengizinkan bobot negatif untuk sebuah koneksi akan membuat algoritma pathfindig diperdebatkan, mungkin kecuali jika Anda membatasi setiap koneksi untuk digunakan hanya sekali.
sumber
Anda dapat menggunakan algoritme dijkstra dengan tepi negatif tidak termasuk siklus negatif, tetapi Anda harus mengizinkan simpul dapat dikunjungi beberapa kali dan versi itu akan kehilangan kerumitan waktu cepatnya.
Dalam hal ini secara praktis saya telah melihat lebih baik menggunakan algoritma SPFA yang memiliki antrian normal dan dapat menangani sisi negatif.
sumber