我可以使用哪种算法来查找图中最短路径的下一个? [英] Which algorithm can I use to find the next to shortest path in a graph?

问题描述

我想找到图中 2 个顶点之间的下一条最短路径，并且该路径具有正成本.允许下一条最短路径共享最短路径的边.我可以使用哪种算法?

I want to find the next shortest path between 2 vertices in a graph and the path has a positive cost.The next shortest path is allowed to share edges of the shortest path .Which algorithm can I use?

推荐答案

我怀疑这在运行时间方面是最佳的，但是:

I doubt this is optimal in terms of running time but:

1. 在图 G 上使用 Dijkstra 算法得到路径 P
2. 对于路径 P 中的所有边 E:
3. -- 如果 G - E 不连通，继续下一个边(转 2)
4. -- 在 G - E 上使用 Dijkstra 算法找到路径 X_i
5. --如果当前X_i的长度比其他所有X_i都短，则保存
6. for 循环末尾的 X_i 是第二个最短路径

第二短路径不能通过 P 中的所有边，但它可能会通过除其中之一之外的所有边.我假设第二最短"是指您不会多次使用边，否则第二最短路径可能包含 P.

The second-shortest path can't go through all edges in P, but it could go through all but one of them, potentially. I assume by "second-shortest" that you don't use edges more than once, otherwise the second-shortest path could contain P.

这篇关于我可以使用哪种算法来查找图中最短路径的下一个?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！