其中的算法，我可以用它来找到一个曲线图旁边的最短路径？ [英] Which algorithm can I use to find the next to shortest path in a graph?

问题描述

我想找到一个图2顶点之间的下一个最短路径和路径有着积极cost.The下一个最短路径被允许共享的最短路径的边缘。其中算法可以使用​​吗？

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. 使用Dijkstra算法对图G获得路径P
2. 对于路径P的所有边E：
3. - 若G - E没有被连接，继续为下沿（进入2）
4. - 使用Dijkstra算法G上 - 电子寻找路径X_i
5. - 如果当前X_i的长度比其他所有X_i短，保存它
6. 的X_i在for循环的结束是第二最短路径

第二最短路径无法通过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屋！