在未知大小的加權有向圖上，如何迭代兩個頂點之間從最短到最長的所有可能的非循環路徑？

Question

我們可以假設所有邊權重都是正數，並且可以枚舉從頂點向外引出的邊，以及在O（1）時間內向內引導的邊。例如，您可以執行Dijkstra遍歷（或帶有可容許啓發式的A *），並標記每個頂點的距離，直到您找到結束頂點，然後在它們描述可能的前輩時反轉這些標記在最佳路徑上。也就是說，對於每個可能的前驅，如果標記的距離之間的差等於連接它們的邊的權重，則可以確定它是否在貪婪的最優路徑上找到。

當考慮可能的前輩時，進入邊的成本加上到每個頂點的最優距離之間的差值等於將該邊包含在解中導致的最優性損失（最優路徑上的邊爲零）。所以也許這個問題變成：如何才能最大限度地延長產量全部可能的路徑按優化程度遞減排列？是否有一種乾淨的方式來執行這種元圖的最佳優先遍歷？

這似乎是一個有用的解決方案的正確方向。也許是爲了記住一個有用的事情是，如果到目前爲止，你已經探索路徑的一部分可能是一個解決方案的一部分是由至少X欠佳，檢查週期只需要沿最後X完成訪問距離（x次優的任何路徑不可能包含比x更長的週期）。

有沒有更高效的方法？

作爲一個獎勵問題，是否也可以在具有負邊權重的圖形上（已知大小）執行此操作？如果引入負循環，它會變得更加困難嗎？ （請記住，因爲我們只查找非循環路徑，所以這並不一定意味着最佳解決方案會失控。）

Answer 1

Credit to n.m .:關於K-shortest-path routing的維基百科文章描述了各種現代化的方法，包括用於Dijkstra泛化的僞代碼，以及鏈接到2011年關於K *的論文，該論文也利用啓發式。

Answer 2

對於N個節點的完整圖，存在（N-2）個數量級！可能從節點A到節點B進行非循環連接。考慮它......這應該是巨大的數字，如果你只需要K（足夠大，但是合理的數量）修改，你最好在評論中提到K-shortest_path。

如果你可以管理足夠的內存來保存所有可能的方法，那麼有一個明顯的解決方案 - 生成所有可能的方法並按重量對它們進行分類。如果沒有，您必須將答案轉儲到磁盤然後收集它們。

您可以使用修改的BFS枚舉所有可能的方法 - 「visited」數組傳遞給遞歸調用，而不是全局布爾數組。當您訪問目的地時，將其添加到全球解決方案地圖（關鍵 - 權重，價值列表）。

如果您無法承擔在內存中保留所有路徑，則可以將它們轉儲爲節奏文件。天真的解決方案：打開名稱爲0的軟件，最多填充10個數字 - 或任何符合您需要的內容 - 重量，併爲路徑添加一行。收集所有程序後，按適當的順序讀取文件並形成最終結果。

注意如果可以，最好不要打開/追加/關閉文件。例如，您可以在地圖上收集路徑，並在路徑總數超過某個限制時僅轉儲最長列表。