在图中找到第二条最短路径（带回溯）

Question

我在LightOJ中发现了一个问题，问题是找到图中从节点1到节点n的第二条最短路径（图中有n个节点标记为从1到n）。现在，问题表明我可以回溯找到第二条最短路径。其中一个示例案例是这样的：

• 从节点 1 到 2 的边，成本 100。
• 从节点 2 到 3 的边，成本 300。
• 从节点 1 到 3 的边，成本 50。

此测试的答案是 150，对于这条路径 1->2->1->3。 我知道 Dijkstra 算法。但我找不到任何关于如何做到这一点的信息。如果这是一个老话题，我很抱歉，但当我用谷歌搜索时，我找不到任何东西。

更新：我读了这个问题。 我可以使用哪种算法来查找图中的下一个最短路径？ 我的问题与它不同，因为在这个问题中，我可以使用边缘两次。我将从节点 1 转到节点 2 一次，然后返回节点 1。这使用了边 1->2 两次。

Answer 1

我认为这可能有用：

维护两个数组：

shortest[i]

和

sec_shortest[i]

，分别表示顶点

i

的最短和第二短路径长度。

现在，您所需要做的就是以稍微不同的方式修改 Dijkstra 算法中

update

部分的方法：

for v in adj(u):
    if shortest[u] + cost(u, v) < shortest[v]:
        sec_shortest[v] = shortest[v]
        shortest[v] = shortest[u] + cost(u, v)
    else if shortest[u] + cost(u, v) < sec_shortest[v]:
            sec_shortest[v] = shortest[u] + cost(u, v)

最后，

sec_shortest[i]

将包含从固定源到顶点

i

的第二短路径长度。

Answer 2

我认为对此有更好的解决方案。首先找到最短路径。假设这条最短路径有 k 条边。

有一个从 i = 1 到 k 的循环，然后每次将路径的第 i_ 条边的值设置为无穷大。之后，运行最短路径算法。并返回您获得的所有 k 个新的最短路径中的最小值。

请注意，您每次都将一条边设置为无穷大。为什么这有效？因为您将得到一条与原始路径的一条边不同的最短路径。

但是，您的问题有点含糊，因为第二最短路径意味着下一个最短路径的成本更高。或者这可能意味着只找到两条不同的最短路径。我在回答中假设是后一种情况。

Answer 3

知道图中的第二个长度很容易，但是如何记录这条路是一个问题。