在圖中找到第二條最短路徑（帶回溯）

Question

我在LightOJ中發現了一個問題，問題是要查找從節點1到節點n的圖中的第二條最短路徑（圖中有n個節點標記爲1到n）。現在，問題表明我可以回溯找到第二條最短路徑。一項所述的樣品的情況下是這樣的：

• 邊緣從節點1到2，花費100
• 邊緣從節點2到3，花費300
• 邊緣從節點1到3，花費50

該測試的答案是150，對於此路徑1-> 2-> 1-> 3。 我知道Dijkstra算法。但我找不到如何做到這一點。我很抱歉，如果這是老話題，但我當我搜索它，我什麼都找不到。

更新：我讀了這個問題。 Which algorithm can I use to find the next to shortest path in a graph? 我的問題不同於它，因爲在這個問題中，我可以使用兩次邊。我從節點1到2一次，然後回到1.這使用邊1-> 2兩次。

Answer 1

我認爲這有更好的解決方案。首先找到最短路徑。假設這條最短路徑有k條邊。

從i = 1到k有一個循環，然後每次設置路徑的第i個邊緣的值爲無窮大。之後，運行最短路徑算法。並返回所有k個新的最短路徑中的最小值。

請注意，每個設置的邊緣都是無限的。爲什麼這個工作？因爲你會得到一條不同於原始邊界的最短路徑。

但是，您的問題有點模棱兩可，因爲第二最短路徑意味着具有嚴格較高成本的下一個最短路徑。或者它可能意味着找到兩條不同的最短路徑。我在回答中假設了後一種情況。