我需要一种在有向图中找到第二条最短路径的方法，而且第二条最短路径不能完全包含最短路径。我知道 dijkstra 算法，但我无法想出一种简单的方法来更改该算法以在合理的时间内给我第二条最短路径。算法、sudo 代码或 c++ 示例，三者之一将不胜感激。
最佳答案
不确定以下是否正确和有效，但这只是一个想法....
第二最短路径至少有一条边不同于最短路径。如果没有节点被访问两次，这也意味着，最短路径中至少有一条边未被第二最短路径使用。
如果那是正确的，你可以先搜索最短路径。然后对于最短路径中的每条边:将其权重设置为无穷大(即从图中排除)并在结果图中搜索最短路径。其中最短的路径应该是原始图中第二短的路径。
关于c++ - 在有向图中找到第二条最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37773839/