我可以使用哪种算法查找图中最短路径的旁边？

Question

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

Answer 1

使用K-shortest路径算法,其中k = 2,一些示例参考:

找到k个最短路径.D.埃普斯坦.第35届IEEE Symp.Comp的基础 Sci.,Santa Fe,1994,pp.154-165.技术.Rep.94-26,ICS,UCI,1994.SiAM J.Computing 28(2):652-673,1998.

该算法实际上非常简单，无需阅读20页：https://en.wikipedia.org/wiki/K_shortest_path_routing#Algorithm (2认同)

Answer 2

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

第二个最短的路径不能通过P中的所有边缘,但它可能会经历除了其中一个之外的所有边缘.我假设"第二短"你不会多次使用边缘,否则第二短路径可能包含P.

我认为算法中存在错误:即使不使用相同的边缘两次,您也可以拥有包含最短路径的第二条最短路径.考虑图:V = {s,m,t},E = {s - > m,m - > t,m - > m},以及为所有边分配1的权重函数.s和t之间的最短路径是:s - > m - > t,第二条最短路径是:s - > m - > m - > t.你的算法不会捕获它. (11认同)
@Guy据我记得，根据定义，一条路径不能两次通过同一顶点。 (2认同)