Mengapa algoritma Dijkstra menggunakan kunci penurunan?

95

Algoritma Dijkstra yang diajarkan kepada saya adalah sebagai berikut

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

Tetapi saya telah melakukan beberapa bacaan tentang algoritme, dan banyak versi yang saya lihat menggunakan tombol pengurang daripada memasukkan.

Mengapa demikian, dan apa perbedaan antara kedua pendekatan tersebut?

algorithm data-structures priority-queue graph-algorithm dijkstra weeb
sumber
14
Downvoter- Bisakah Anda menjelaskan apa yang salah dengan pertanyaan ini? Saya pikir itu sangat adil, dan banyak orang (termasuk saya) pertama kali diperkenalkan ke versi Dijkstra OP daripada versi kunci penurunan.
templatetypedef

Jawaban:

71

Alasan untuk menggunakan kunci penurunan daripada memasukkan kembali node adalah untuk menjaga jumlah node dalam antrian prioritas kecil, sehingga menjaga jumlah total antrian prioritas kecil dan biaya setiap keseimbangan antrian prioritas rendah.

Dalam implementasi algoritma Dijkstra yang memasukkan kembali node ke dalam antrian prioritas dengan prioritas barunya, satu node ditambahkan ke antrian prioritas untuk setiap m edge dalam grafik. Ini berarti bahwa ada operasi antrian dan m operasi dequeue pada antrian prioritas, memberikan total runtime dari O (m T e + m T d ), di mana T e adalah waktu yang dibutuhkan untuk masuk ke antrian prioritas dan T d adalah waktu yang diperlukan untuk membatalkan antrean prioritas.

Dalam implementasi algoritma Dijkstra yang mendukung kunci-penurunan, antrian prioritas yang menahan node dimulai dengan n node di dalamnya dan pada setiap langkah algoritma menghapus satu node. Ini berarti jumlah heap dequeue adalah n. Setiap node akan memiliki kunci penurunan yang dipanggil secara potensial sekali untuk setiap tepi yang mengarah ke dalamnya, sehingga jumlah total kunci penurunan yang dilakukan paling banyak m. Ini memberikan runtime (n T e + n T d + m T k ), di mana T k adalah waktu yang dibutuhkan untuk memanggil tombol-menurun.

Jadi, apa efeknya pada runtime? Itu tergantung pada antrian prioritas apa yang Anda gunakan. Berikut adalah tabel singkat yang menunjukkan antrian prioritas yang berbeda dan keseluruhan runtime dari implementasi algoritma Dijkstra yang berbeda:

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

Seperti yang Anda lihat, dengan sebagian besar jenis antrean prioritas, sebenarnya tidak ada perbedaan dalam runtime asimtotik, dan versi kunci kecil kemungkinan tidak akan bekerja lebih baik. Namun, jika Anda menggunakan implementasi tumpukan Fibonacci dari antrian prioritas, maka memang algoritme Dijkstra akan lebih efisien secara asimtotik saat menggunakan kunci penurunan.

Singkatnya, menggunakan kunci penurunan, ditambah antrean prioritas yang baik, dapat menghilangkan waktu proses asimtotik Dijkstra melebihi kemungkinan jika Anda terus melakukan antrean dan antrean.

Selain poin ini, beberapa algoritma yang lebih maju, seperti Algoritma Jalur Terpendek Gabow, menggunakan algoritma Dijkstra sebagai subrutin dan sangat bergantung pada implementasi kunci penurunan. Mereka menggunakan fakta bahwa jika Anda mengetahui kisaran jarak yang valid sebelumnya, Anda dapat membangun antrian prioritas super efisien berdasarkan fakta tersebut.

Semoga ini membantu!

templatetypedef
sumber
1
+1: Saya lupa memperhitungkan heap. Satu quibble, karena heap versi insert memiliki node per edge, yaitu O (m), bukankah waktu aksesnya harus O (log m), memberikan total run time O (m log m)? Maksud saya, dalam grafik normal m tidak lebih besar dari n ^ 2, jadi ini berkurang menjadi O (m log n), tetapi dalam grafik di mana dua node dapat digabungkan dengan beberapa tepi dengan bobot berbeda, m tidak dibatasi (tentu saja , kita dapat mengklaim bahwa jalur minimum antara dua node hanya menggunakan tepi minimal, dan menguranginya menjadi grafik normal, tetapi untuk nonce, ini menarik).
rampion
2
@ Rampion- Anda benar, tetapi karena saya pikir secara umum diasumsikan bahwa tepi paralel telah dikurangi sebelum menjalankan algoritma, saya tidak berpikir bahwa O (log n) versus O (log m) akan menjadi masalah. Biasanya m diasumsikan sebagai O (n ^ 2).
templatetypedef
28

Pada tahun 2007, ada makalah yang mempelajari perbedaan waktu eksekusi antara menggunakan versi kunci penurunan dan versi sisipan. Lihat http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Kesimpulan dasar mereka adalah tidak menggunakan kunci penurunan untuk sebagian besar grafik. Khusus untuk grafik renggang, kunci non-penurunan jauh lebih cepat daripada versi kunci penurunan. Lihat kertas untuk lebih jelasnya.

Marc Meketon
sumber
7
cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf adalah tautan yang berfungsi untuk makalah itu.
eleanora
PERINGATAN: ada bug di kertas yang ditautkan. Halaman 16, fungsi B.2: if k < d[u]seharusnya if k <= d[u].
Xeverous
2

Ada dua cara untuk mengimplementasikan Dijkstra: satu menggunakan heap yang mendukung kunci-penurunan dan satu lagi heap yang tidak mendukung itu.

Keduanya valid secara umum, tetapi yang terakhir biasanya lebih disukai. Berikut ini saya akan menggunakan 'm' untuk menunjukkan jumlah sisi dan 'n' untuk menunjukkan jumlah simpul dari grafik kita:

Jika Anda menginginkan kompleksitas kasus terburuk sebaik mungkin, Anda akan menggunakan tumpukan Fibonacci yang mendukung kunci penurunan: Anda akan mendapatkan O (m + nlogn) yang bagus.

Jika Anda peduli dengan kasus rata-rata, Anda dapat menggunakan tumpukan Biner juga: Anda akan mendapatkan O (m + nlog (m / n) logn). Bukti ada di sini , halaman 99/100. Jika grafiknya padat (m >> n), grafik yang satu ini dan yang sebelumnya cenderung ke O (m).

Jika Anda ingin mengetahui apa yang terjadi jika Anda menjalankannya pada grafik nyata, Anda dapat memeriksa makalah ini , seperti yang disarankan Mark Meketon dalam jawabannya.

Hasil eksperimen akan menunjukkan bahwa heap yang "lebih sederhana" akan memberikan hasil terbaik dalam banyak kasus.

Faktanya, di antara implementasi yang menggunakan kunci penurunan, Dijkstra berkinerja lebih baik saat menggunakan heap Biner sederhana atau heap Pairing daripada saat menggunakan heap Fibonacci. Ini karena tumpukan Fibonacci melibatkan faktor konstanta yang lebih besar dan jumlah aktual operasi kunci penurunan cenderung jauh lebih kecil daripada prediksi kasus terburuk.

Untuk alasan yang serupa, heap yang tidak harus mendukung operasi kunci-penurunan, memiliki faktor yang kurang konstan dan benar-benar berkinerja terbaik. Apalagi jika grafiknya jarang.

Nicola Amadio
sumber