c++ - 在图中查找第二条最短路径(使用回溯)

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

我认为这可能有效:

维护两个数组: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 的第二最短路径长度。