Menemukan jalur k-terpendek antara dua node

Dengan diberi digraf tertimbang , dan fungsi bobot, , orang biasanya dapat menggunakan algoritma Dijkstra untuk mendapatkan jalur terpendek. Apa yang saya tertarik, adalah bagaimana cara mendapatkan jalur terpendek, terpendek, dan sebagainya. $G=V,E$ $d(u,v)$ $2^{nd}$ $3^{rd}$

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$

algorithms graphs shortest-path graph-traversal Realz Slaw
sumber

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 Buat jawaban, dengan ringkasan singkat?

Raphael

Jawaban:

$k$ $k$ $O(m+n \log n + 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