Mengapa algoritma Dijkstra tidak bekerja untuk tepi berbobot negatif?

121

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.

Madu
sumber
3
Jawaban yang benar dengan contoh yang bagus adalah: stackoverflow.com/questions/6799172/…
Amitk

Jawaban:

175

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:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

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.

amit
sumber
5
Maaf, tetapi saya tidak mendapatkan kesalahan apa pun. Pertama A->Bakan 5 dan A->Cakan 2. Kemudian B->Cakan -5. Jadi nilainya Cakan -5sama dengan bellman-ford. Bagaimana ini tidak memberikan jawaban yang benar?
Anirban Nag 'tintinmj'
5
@tintinmj dulu, Dijkstra akan "menutup" node Adengan nilai 0. Kemudian akan melihat node yang bernilai minimal, Badalah 5 dan C2. Minimal adalah C, sehingga akan menutup Cdengan nilai 2 dan tidak akan pernah melihat ke belakang, ketika nanti Bditutup, tidak dapat mengubah nilai C, karena sudah "ditutup".
amit
4
@amit Bagaimana algoritma Dijkstra tidak menemukan jalannya A -> B -> C? Ini pertama-tama akan memperbarui Cjarak ke 2, dan kemudian Bjarak ke 5. Dengan asumsi bahwa dalam grafik Anda tidak ada tepi keluar dari C, maka kami tidak melakukan apa-apa saat mengunjungi C(dan jaraknya masih 2). Kemudian kita mengunjungi Dnode yang berdekatan, dan satu-satunya node yang berdekatan adalah C, yang jarak barunya -5. Perhatikan bahwa dalam algoritma Dijkstra, kita juga melacak induk dari mana kita menjangkau (dan memperbarui) simpul, dan melakukannya C, Anda akan mendapatkan induk B, dan kemudian A, menghasilkan hasil yang benar. Apa yang saya lewatkan?
nbro
12
@amit Masalah dengan penalaran Anda (saya pikir), dan saya telah melihat orang lain melakukannya (anehnya), adalah bahwa Anda berpikir algoritme tidak akan mempertimbangkan kembali node yang jarak terpendeknya telah ditentukan (dan kita sudah selesai), tetapi ini tidak benar, dan itulah mengapa kami memiliki langkah "relaksasi" ... Kami melakukan iterasi melalui semua node grafik, dan, untuk masing-masing, kami mengulang melalui node yang berdekatan, bahkan jika salah satu node yang berdekatan mungkin telah dihapus dari antrian prioritas-min kami, misalnya.
nbro
10
@amit Periksa jawaban ini untuk pertanyaan serupa, yang contoh sebenarnya masuk akal: stackoverflow.com/a/6799344/3924118
nbro
37

Pertimbangkan grafik yang ditunjukkan di bawah ini dengan sumber sebagai Vertex A. Pertama coba jalankan sendiri algoritma Dijkstra di atasnya.

masukkan deskripsi gambar di sini

Ketika saya mengacu pada algoritma Dijkstra dalam penjelasan saya, saya akan berbicara tentang Algoritma Dijkstra seperti yang diterapkan di bawah ini,

Algoritma Dijkstra

Jadi memulai nilai ( jarak dari sumber ke simpul ) yang awalnya ditetapkan untuk setiap simpul adalah,

inisialisasi

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,

iterasi pertama

Sekarang kita mengekstrak C sebagai (2 <5), sekarang Q = [B] . Perhatikan bahwa C tidak terhubung ke apa-apa, jadi line16loop tidak berjalan.

iterasi kedua

Akhirnya kami mengekstrak B, setelah itu Q adalah Phi. Catatan B memiliki tepi terarah ke C tetapi C tidak ada di Q oleh karena itu kami sekali lagi tidak memasukkan perulangan for line16,

3?

Jadi kami berakhir dengan jarak sebagai

tidak ada perubahan guys

Perhatikan bagaimana ini salah karena jarak terpendek dari A ke C adalah 5 + -10 = -5, saat Anda pergi a ke b ke c.

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 line16loop 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 line16mereka memeriksa semua tetangga v (yaitu tepi diarahkan ada dari u ke v ), dari u yang masih dalam Q . Di line14dalamnya mereka menghapus catatan yang dikunjungi dari Q. Jadi jika x adalah tetangga yang dikunjungi dari u , jalur sumber ke u sampai xtersebut 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 A ke B ke Ctersebut tidak dipertimbangkan, meninggalkan jalur terpendek saat ini A sampai Ctidak 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 - tidak memungkinkanyang 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 13jarak 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.

Jadi setiap kalkulasi dist [x] yang kita buat akan menjadi tidak benar jika x dihilangkan sebelum semua simpul v - sehingga x adalah tetangga dari v dengan sisi negatif menghubungkannya - dihilangkan.

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.

Aditya P.
sumber
2
Seperti yang Anda katakan, cara yang lebih baik untuk menyelesaikan ini adalah dengan menggunakan metode heapq.heappush setelah setiap perbandingan. Kami mendorong kembali jarak yang diperbarui ke dalam antrian. Dalam kondisi ini, Dijkstra dapat bekerja pada bobot negatif. Saya mencoba, dan hasilnya 0,5, -5
nosense
1
"jalur sumber ke x ke u bahkan tidak dipertimbangkan"; maksud Anda sumber untuk u ke x?
slmatrix
1
@slmatrix terima kasih untuk menangkapnya, ya, maksud saya jalur dari sumber ke u ke x, karena x adalah tetangga dari u.
Aditya P
23

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.

zmbq
sumber
8

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.

Nikunj Banka
sumber
6

Coba algoritma Dijkstra pada grafik berikut, dengan asumsi Anode sumber, untuk melihat apa yang terjadi:

Grafik

tb-
sumber
6
Maaf, tetapi saya tidak mendapatkan kesalahan apa pun. Pertama A->Bakan 1dan A->Cakan 100. Lalu B->Dakan 2. Lalu C->Dakan -4900. Jadi nilainya Dakan -4900sama dengan bellman-ford. Bagaimana ini tidak memberikan jawaban yang benar?
Anirban Nag 'tintinmj'
9
@tintinmj Jika Anda memiliki tepi keluar dari D, tepi tersebut akan dikunjungi sebelum jarak D dikurangi dan karenanya tidak diperbarui setelah itu. Ini kemudian akan menghasilkan kesalahan yang pasti. Jika Anda menganggap D's 2 sebagai jarak terakhir setelah memindai tepi keluar, bahkan grafik ini menghasilkan kesalahan.
Christian Schnorr
@ tb- Maaf sudah bertanya setelah sekian lama tetapi, apakah saya di jalur yang benar di sini? Pertama A->Bakan 1dan A->Cakan menjadi 100. Kemudian Bdieksplorasi dan diatur B->Dke 2. Lalu D dieksplorasi karena saat ini ia memiliki jalur terpendek kembali ke sumbernya? Apakah saya benar mengatakan bahwa jika B->Ddulu 100, Cakankah dieksplorasi terlebih dahulu? Saya memahami semua contoh lain yang diberikan orang kecuali Anda.
Pejman Poh
@PejmanPoh dari pemahaman saya, jika B-> D adalah 100, karena A-> C lebih tinggi di HeapStructure yang akan digunakan, ekstrak min akan mengembalikan A-> C pertama yang berarti jalur terpendek yang ditemukan berikutnya akan menjadi jalur ke C, setelah itu jalur dari C-> D dengan bobot -5000 akan menjadi pilihan yang jelas, membawa kita pada kesimpulan bahwa jalur terpendek adalah dari A-> C-> D dan saya cukup yakin ini akan jadilah perilaku normal. Jadi kadang-kadang ketika kita memiliki siklus negatif kita mungkin masih mendapatkan nilai yang tepat untuk jalur terpendek, tetapi jelas tidak selalu, ini adalah contoh di mana kita tidak akan ..
T.Dimitrov
1

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.

vineet
sumber
0

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:

A  <- 5 ->  B  <- (-1) ->  C <- 5 -> D

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.

Dakkaron
sumber
0

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.

CodingLab
sumber