訪問k個頂點的無向圖中的最短路徑

Question

考慮一個無向圖。有n個頂點和m個邊。所有的邊都有一個與之相關的重量。

我想設備一個算法，將採取源頂點's'，水槽頂點't'和數字'k'作爲輸入。算法的輸出是從s到t之間具有k個頂點的最短路徑。

請建議。謝謝！

Answer 1

創建與您的圖形關聯的[numvertices] [numvertices]的距離矩陣。然後運行Floyd算法，但只是k次迭代而不是numvertices迭代。

Answer 2

經過小小的研究，我發現這個問題是NP-Hard。因此我必須使用參數化技術來解決這個問題。我用過的算法是一個固定參數可處理的算法。

我在我的算法中使用了Lawler's modification of the Yen's algorithm來解決這個問題。 Yen的算法有助於找出無環路網絡中前n條最短路徑。這裏是我的算法怎麼一回事：

1. 獲取參數k從用戶（在路徑頂點數目）。同樣從用戶那裏得到'm'，這是路徑不應超過的最大距離。這是將幫助我們在多項式時間內解決NP-Hard問題的參數。

2. 這一步使用Yen的算法。找到下一個最短路徑。檢查路徑是否有k個頂點。

   a。如果是，則中止並返回路徑 b。否則，2

3. 如果路徑的總距離超過參數「m」，則跳過和返回「無結果」

日元的算法使用Dijkstra算法找到最短路徑。實現這個算法解決這個問題很有趣。