搜索K-first短路徑算法

Question

我發現了許多算法和方法，這些算法和方法討論尋找最短路徑或問題的最佳/最優解決方案。但是，我想要做的是找到從一個點到另一個點的第一個K最短路徑的算法。我面臨的問題更像是通過樹進行搜索，在每一步中，每個步驟都有多個選項。使用哪種算法來面對這類問題？

Answer 1

There is the 2006 paper by Jose Santos 比較三種不同的K-最短尋路算法。

Answer 2

日元的算法實現： http://code.google.com/p/k-shortest-paths/

更簡單的算法&討論： Suggestions for KSPA on undirected graph

Answer 3

編輯：顯然我點擊了一個鏈接，因爲我覺得我是在回答到一個新的問題;如果 - 很可能 - 忽略這個問題 - 這個問題對你來說並不重要。

---

鑑於您正在處理的問題的限制版本，這變得更容易實現。需要注意的最重要的事情是，在樹中，最短路徑是兩個節點之間的唯一路徑。所以你要做的就是解決所有對最短路徑，即樹中的O(n²)做n BFS遍歷，然後你得到最小值k。這可能可以通過某種方式進行優化，但這種做法的天真方法是對O(n² log n)時間的O(n²)距離進行排序，並將k的最小值進行排序;通過一些記錄，您可以跟蹤哪個距離對應於哪條路徑，而無需時間複雜性開銷。這會比使用KSPA算法的O(n²)可能的s-t對更好的複雜性。

---

如果你實際上意味着是固定源，並得到與來自該源的最小距離的k節點，一個BFS會做。如果你的意思是固定源和目標，那麼一個BFS就足夠了。

---

我不看你如何使用的事實，下面從節點去節點的水平邊緣都具有相同的權重不知道更多關於樹的結構。