在直接圖中找到第二條最短路徑

Question

我需要一種方法來找到有向圖中的第二條最短路徑，在第二條最短路徑上不能完全包含最短路徑。我意識到dijkstra算法，但是我無法找到一個簡單的方法來改變算法，在合理的時間內給我第二短的路徑。算法，sudo-code或C++的例子，三者之一將不勝感激。

Answer 1

不知道下面是正確的作品，但它只是一個想法....

第二最短路徑，從最短路徑不同的至少一個邊緣。如果沒有節點被訪問兩次，這也意味着最短路徑中至少存在一條未被第二條最短路徑使用的邊。

如果這是正確的，你可以先搜索最短路徑。然後，對於最短路徑中的每條邊：將其權重設置爲無窮大（即將其從圖中排除）並在結果圖中搜索最短路徑。其中最短的路徑應該是原始圖中的第二短路徑。