Bobot negatif menggunakan Algoritma Dijkstra

Saya mencoba memahami mengapa algoritma Dijkstra tidak akan bekerja dengan bobot negatif. Membaca contoh di Jalur Terpendek , saya mencoba mencari tahu skenario berikut:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

Dari situs web:

Dengan asumsi edge semua terarah dari kiri ke kanan, Jika kita mulai dengan A, algoritma Dijkstra akan memilih edge (A, x) meminimalkan d (A, A) + length (edge), yaitu (A, B). Ini kemudian menetapkan d (A, B) = 2 dan memilih sisi lain (y, C) meminimalkan d (A, y) + d (y, C); satu-satunya pilihan adalah (A, C) dan menetapkan d (A, C) = 3. Tetapi ia tidak pernah menemukan jalur terpendek dari A ke B, melalui C, dengan total panjang 1.

Saya tidak dapat memahami mengapa menggunakan implementasi Dijkstra berikut, d [B] tidak akan diperbarui ke 1(Ketika algoritme mencapai simpul C, itu akan berjalan santai di B, lihat bahwa d [B] sama dengan 2, dan karenanya perbarui nilainya menjadi 1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ← Ø
   Q ← V[G]//priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v  V(G)
      d[v] ← ∞
      π[v] ← NIL
   d[s] ← 0
}

Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      π[v] ← u
      Update(Q, v)
}

Terima kasih,

Meir

Algoritme yang Anda sarankan memang akan menemukan jalur terpendek dalam grafik ini, tetapi tidak semua grafik secara umum. Misalnya, perhatikan grafik ini:

Asumsikan tepi diarahkan dari kiri ke kanan seperti pada contoh Anda,

Algoritme Anda akan berfungsi sebagai berikut:

1. Pertama, Anda menyetel d(A)ke zerodan jarak lainnya ke infinity.
2. Anda kemudian memperluas node A, menyetel d(B)ke 1, d(C)ke zero, dan d(D)ke 99.
3. Selanjutnya, Anda melakukan ekspansi C, tanpa perubahan bersih.
4. Anda kemudian mengembangkannya B, yang tidak berpengaruh.
5. Akhirnya, Anda memperluas D, yang berubah d(B)menjadi -201.

Perhatikan bahwa pada akhir ini, meskipun, itu d(C)tetap 0, meskipun jalur terpendek Cmemiliki panjang -200. Algoritme Anda karenanya gagal menghitung jarak secara akurat dalam beberapa kasus. Selain itu, bahkan jika Anda menyimpan kembali petunjuk yang mengatakan bagaimana untuk pergi dari setiap node ke node awal A, Anda akan berakhir mengambil jalur yang salah kembali dari Cke A.

Perhatikan, Dijkstra bekerja bahkan untuk bobot negatif, jika Grafik tidak memiliki siklus negatif, yaitu siklus yang bobotnya dijumlahkan kurang dari nol.

Mungkin ada yang bertanya, kenapa pada contoh yang dibuat oleh templatetypedef Dijkstra gagal padahal tidak ada siklus negatif, bahkan tidak ada siklus. Itu karena dia menggunakan kriteria stop lain, yang menahan algoritme segera setelah node target tercapai (atau semua node telah diselesaikan satu kali, dia tidak menentukannya dengan tepat). Dalam grafik tanpa bobot negatif, ini berfungsi dengan baik.

Jika seseorang menggunakan kriteria stop alternatif, yang menghentikan algoritma ketika prioritas-antrian (heap) berjalan kosong (kriteria stop ini juga digunakan dalam pertanyaan), maka dijkstra akan menemukan jarak yang benar bahkan untuk grafik dengan bobot negatif tapi tanpa siklus negatif.

Namun, dalam kasus ini, batas waktu asimtotik dijkstra untuk grafik tanpa siklus negatif hilang. Ini karena node yang sebelumnya diselesaikan dapat dimasukkan kembali ke heap ketika jarak yang lebih baik ditemukan karena bobot negatif. Properti ini disebut koreksi label.

Anda tidak menggunakan S di mana pun dalam algoritme Anda (selain memodifikasinya). Ide dari dijkstra adalah sekali sebuah simpul berada di S, itu tidak akan pernah dimodifikasi lagi. dalam hal ini, setelah B berada di dalam S, Anda tidak akan mencapainya lagi melalui C.

fakta ini memastikan kompleksitas O (E + VlogV) [jika tidak, Anda akan mengulang tepian lebih dari sekali, dan simpul lebih dari sekali]

dengan kata lain, algoritma yang Anda posting, mungkin tidak dalam O (E + VlogV), seperti yang dijanjikan oleh algoritma dijkstra.

Karena Dijkstra adalah pendekatan Greedy, sekali simpul ditandai sebagai dikunjungi untuk loop ini, itu tidak akan pernah dievaluasi ulang lagi bahkan jika ada jalur lain dengan biaya lebih sedikit untuk mencapainya nanti. Dan masalah seperti itu hanya bisa terjadi jika tepi negatif ada di grafik.

Sebuah algoritma serakah , seperti namanya, selalu membuat pilihan yang tampaknya menjadi yang terbaik pada saat itu. Asumsikan bahwa Anda memiliki fungsi objektif yang perlu dioptimalkan (baik dimaksimalkan atau diminimalkan) pada titik tertentu. Algoritme Greedy membuat pilihan serakah di setiap langkah untuk memastikan bahwa fungsi tujuan dioptimalkan. Algoritme Greedy hanya memiliki satu kesempatan untuk menghitung solusi optimal sehingga tidak pernah mundur dan membalikkan keputusan.

TL; DR: Jawabannya tergantung pada implementasi Anda. Untuk kode pseudo yang Anda posting, ini berfungsi dengan bobot negatif.

Varian Algoritma Dijkstra

Kuncinya adalah ada 3 macam implementasi algoritma Dijkstra , tetapi semua jawaban di bawah pertanyaan ini mengabaikan perbedaan di antara varian-varian ini.

1. Menggunakan -loop bersarangfor untuk melemaskan simpul. Ini adalah cara termudah untuk mengimplementasikan algoritma Dijkstra. Kompleksitas waktu adalah O (V ^ 2).
2. Implementasi berbasis antrean prioritas / tumpukan + TIDAK boleh masuk kembali, di mana masuk kembali berarti simpul yang santai dapat didorong ke antrean-prioritas lagi untuk dilonggarkan lagi nanti .
3. Penerapan berbasis antrean / tumpukan prioritas + masuk kembali diizinkan.

Versi 1 & 2 akan gagal pada grafik dengan bobot negatif (jika Anda mendapatkan jawaban yang benar dalam kasus seperti itu, itu hanya kebetulan), tetapi versi 3 masih berfungsi .

Kode pseudo yang diposting di bawah masalah asli adalah versi 3 di atas, sehingga berfungsi dengan bobot negatif.

Berikut adalah referensi yang bagus dari Algoritma (edisi ke-4) , yang mengatakan (dan berisi implementasi java versi 2 & 3 yang saya sebutkan di atas):

T. Apakah algoritma Dijkstra bekerja dengan bobot negatif?

A. Ya dan tidak. Ada dua algoritme jalur terpendek yang dikenal sebagai algoritme Dijkstra, bergantung pada apakah sebuah simpul dapat diantrekan pada antrean prioritas lebih dari sekali. Jika bobotnya bukan negatif, kedua versi tersebut bertepatan (karena tidak ada simpul yang akan diantrekan lebih dari satu kali). Versi yang diimplementasikan di DijkstraSP.java (yang memungkinkan sebuah simpul untuk diantrekan lebih dari satu kali) benar dengan adanya bobot tepi negatif (tetapi tidak ada siklus negatif) tetapi waktu berjalannya eksponensial dalam kasus terburuk. (Kami mencatat bahwa DijkstraSP.java melontarkan pengecualian jika digraf edge-weighted memiliki edge dengan bobot negatif, sehingga programmer tidak terkejut dengan perilaku eksponensial ini.) Jika kita memodifikasi DijkstraSP.java sehingga simpul tidak dapat diantrekan lebih dari sekali (misalnya, menggunakan larik [] yang ditandai untuk menandai simpul yang telah dikendurkan),

Untuk detail implementasi lebih lanjut dan koneksi versi 3 dengan algoritma Bellman-Ford, silakan lihat jawaban ini dari zhihu . Itu juga jawaban saya (tapi dalam bahasa Mandarin). Saat ini saya tidak punya waktu untuk menerjemahkannya ke dalam bahasa Inggris. Saya sangat menghargai jika seseorang dapat melakukan ini dan mengedit jawaban ini di stackoverflow.

Pertimbangkan apa yang terjadi jika Anda bolak-balik antara B dan C ... voila

(hanya relevan jika grafik tidak diarahkan)

Diedit: Saya yakin masalahnya ada hubungannya dengan fakta bahwa jalur dengan AC * hanya bisa lebih baik daripada AB dengan adanya tepi berbobot negatif, jadi tidak masalah ke mana Anda pergi setelah AC, dengan asumsi non- tepi berbobot negatif tidak mungkin menemukan jalur yang lebih baik daripada AB setelah Anda memilih untuk mencapai B setelah pergi AC.

"2) Dapatkah kita menggunakan algoritme Dijksra untuk jalur terpendek untuk grafik dengan bobot negatif - satu gagasan dapat berupa, hitung nilai bobot minimum, tambahkan nilai positif (sama dengan nilai absolut dari nilai bobot minimum) ke semua bobot dan jalankan algoritme Dijksra untuk grafik yang dimodifikasi. Apakah algoritme ini akan berfungsi? "

Ini sama sekali tidak berfungsi kecuali semua jalur terpendek memiliki panjang yang sama. Misalnya diberi jalur terpendek dengan panjang dua sisi, dan setelah menambahkan nilai absolut ke setiap sisi, maka total biaya jalur dinaikkan sebesar 2 * | bobot negatif maks |. Di sisi lain jalur lain dengan panjang tiga sisi, sehingga biaya jalur meningkat 3 * | bobot negatif maks |. Oleh karena itu, semua jalur yang berbeda ditingkatkan dengan jumlah yang berbeda.

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.