Memodifikasi algoritma Dijkstra untuk bobot tepi yang diambil dari rentang

Misalkan saya memiliki grafik berarah dengan bobot tepi yang diambil dari rentang mana K adalah konstan. Jika saya mencoba menemukan jalur terpendek menggunakan algoritma Dijkstra , bagaimana saya bisa memodifikasi algoritma / struktur data dan meningkatkan kompleksitas waktu menjadi O ( | V | + | E | ) ?$[1,\dots, K]$$K$$O(|V|+|E|)$

Jika bobot tepi bilangan bulat dalam , Anda dapat mengimplementasikan Dijkstra untuk dijalankan dalam waktu O ( K | V | + | E | ) , mengikuti saran @rrenaud. Berikut ini penjelasan yang lebih eksplisit.$\{0,1,\ldots,K\}$$O(K|V|+|E|)$

Kapan saja, kunci (hingga) dalam antrian prioritas berada dalam beberapa rentang , di mana D adalah nilai kunci terakhir yang dihapus dari antrian prioritas. (Setiap kunci setidaknya D , karena urutan kunci dihapus oleh algoritma Dijkstra adalah non-menurun, dan setiap kunci yang paling banyak D + K , karena setiap tombol memiliki nilai d [ u ] + w t ( u , w ) untuk beberapa tepi ( u $\{D,D+1,\ldots,D+K\}$$D$$D$$D+K$$d[u] + wt(u,w)$ mana d [ u ] adalah jarak dari sumber ke beberapa simpul u yang telah dihapus, jadi d [ u ] ≤ D. )$(u,w)$$d[u]$$u$$d[u]\le D$

Karena itu, Anda dapat menerapkan antrian prioritas dengan array melingkar dengan ukuran K + 1 , dengan setiap sel berisi ember. Simpan setiap simpul dengan kunci k dalam ember di sel A [ h ( k ) ] di mana . Melacak . Lakukan operasi sebagai berikut:$A[0..K]$$K+1$$k$$A[h(k)]$$h(k)=k \bmod (K+1)$$D$

• menghapus-min : Sementara kosong, kenaikan . Kemudian hapus dan kembalikan simpul dari .$A[h(D)]$$D$$A[h(D)]$

• masukkan dengan kunci : Tambahkan simpul ke ember .$k$$A[h(k)]$

• tombol-turun ke : Memindahkan titik dari ke .$k$$k'$$A[h(k)]$$A[h(k')]$

Memasukkan dan mengurangi kunci adalah operasi waktu konstan, sehingga total waktu yang dihabiskan dalam operasi tersebut adalah . Total waktu yang dihabiskan di delete-min akan ditambah nilai akhir dari . Nilai akhir dari adalah maksimum (terbatas) jarak dari sumber ke setiap simpul (karena menghapus-min yang mengambil iterasi meningkat oleh ). Jarak maksimum paling banyak karena setiap jalur memiliki paling banyak tepi. Dengan demikian, total waktu yang dihabiskan oleh algoritma adalah .$O(|V|+|E|)$$O(|V|)$$D$$D$$i$$D$$i$$K(|V|-1)$$|V|-1$$O(K|V|+|E|)$

Saya berasumsi di sini bahwa adalah bilangan bulat dan bobot ujung adalah integral. Kalau tidak benar-benar tidak membeli apa-apa, Anda selalu dapat menskala ulang bobot sehingga min edge memiliki biaya dan max memiliki biaya , sehingga masalahnya identik dengan masalah jalur terpendek standar.$K$$1$$K$

Algoritma / sketsa bukti: Menerapkan antrian prioritas dengan cara gila seperti ini sebagai arraydaftar dikunci oleh biaya dan sebaliknya menggunakan algoritma Dijkstra standar. Simpan penghitung yang melacak biaya item minimum di heap. Selesaikan panggilan dequeue setelah item dihapus dengan pemindaian linier . Ya, ini kedengarannya gila, tetapi konstanta memungkinkan Anda menipu dan menipu intuisi algoritme Anda terhadap pemindaian linier. Anda hanya perlu memindai dari penanda min terakhir karena algoritma Disjkstra bagus untuk implementasi antrian Anda. Pada saat ia meminta dequeue, item yang dimasukkan ke dalam antrian selalu lebih besar atau sama dengan minimum sebelumnya. Jalur terpendek yang terpanjang yang mungkin memiliki panjang$K\times |V|$$K$$K\times |V|$, jadi biaya pemindaian yang diamortisasi adalah jika K adalah konstan.$K\times |V| = O(|V|)$

Anda dapat menggunakan jenis topologi untuk menemukan solusinya, biarkan sumber memiliki derajat 0 lalu, pergi dari setiap tepi dari sumber, jika simpul lain memiliki 0 derajat kemudian masukkan ke dalam antrian dan terus lakukan itu. dalam hal ini (tanpa siklus di dalam grafik) dapat mencapai V + E karena akan melalui setiap titik dan ujung sekali dan hanya sekali.