Menemukan jalur k-terpendek antara dua node

9

Dengan diberi digraf tertimbang , dan fungsi bobot, d ( u , v ) , orang biasanya dapat menggunakan algoritma Dijkstra untuk mendapatkan jalur terpendek. Apa yang saya tertarik, adalah bagaimana cara mendapatkan 2 n d- jalur terpendek, 3 r d- terpendek, dan sebagainya.G=V,Ed(kamu,v)2nd3rd

Pertanyaan:

Apakah ada algoritma yang efisien untuk mendapatkan jalur ke-i-ke-terpendek antara dua node dalam grafik berbobot?

Apakah ada algoritma yang efisien untuk mendapatkan k-path paling pendek antara dua node dalam grafik berbobot?

Jawaban untuk salah satu adalah OK, meskipun saya bertanya-tanya apakah jawaban untuk pertanyaan kedua dapat dilakukan lebih efisien daripada panggilan ke jawaban untuk pertanyaan pertama.k

Realz Slaw
sumber
2
Pencarian Google pada "k shortest paths" menghasilkan sejumlah referensi yang menjelaskan algoritma untuk masalah ini. Ada juga artikel Wikipedia tentang topik ini: en.wikipedia.org/wiki/K_shortest_path_routing
DW
@DW Buat jawaban, dengan ringkasan singkat?
Raphael

Jawaban:

5

kkHAI(m+ncatatann+k)k jalur terpendek (memungkinkan siklus) antara sepasang simpul dalam digraf. Dengan teknik-teknik makalah ini, seseorang juga dapat menemukan semua jalur lebih pendek dari batas tertentu, dalam batas waktu yang sama. Ada banyak literatur tentang masalah ini, makalah Eppstein mencakup banyak referensi dan diskusi.

Jika Anda melarang siklus, Anda mungkin ingin melihat algoritma Hershberger et al. [2].


[1] Eppstein, David. "Menemukan k jalur terpendek." Jurnal SIAM tentang komputasi 28.2 (1998): 652-673. [ CiteSeerX ]

[2] Hershberger, John, Matthew Maxel, dan Subhash Suri. "Menemukan jalur sederhana k terpendek: Algoritma baru dan implementasinya." Transaksi ACM tentang Algoritma (TALG) 3.4 (2007): 45. [ CiteSeerX ]

Juho
sumber