问求任意两个结点间多权边的最短路径
EN

Stack Overflow用户

提问于 2015-04-19 01:38:21

回答 1查看 1.2K关注 0票数 3

当有多条边具有不同的权重从一个节点移动到另一个节点时，我们如何使用Dijkstra算法来找到最短路径，并且从一种模式到另一种模式的边的可用性取决于您到达该路径所采用的边。

这就是在任意两个车站之间有多个火车/航班，并且到达任何中间节点的时间至少应在下一次航班/火车出发时间之前几个小时的情况下，对最便宜路径的行程规划的情况。

发布于 2015-04-19 19:10:11

这个问题在算法设计手册第4.4章-战争故事:在飞机上给我一张票中讨论过。

你可以在这里找到：http://sist.sysu.edu.cn/~isslxm/DSA/textbook/Skiena.-.TheAlgorithmDesignManual.pdf (第118页)

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/29720633

复制

相似问题

问求任意两个结点间多权边的最短路径EN