一尘不染

我可以使用哪种算法在图中找到最短的路径?

algorithm

我想在图形中的两个顶点之间找到下一条最短路径,并且该路径的成本为正。允许下一条最短路径共享最短路径的边,我可以使用哪种算法?


阅读 226

收藏
2020-07-28

共1个答案

一尘不染

我怀疑这对于运行时间是否最佳,但是:

  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。

2020-07-28