我正在寻找一种算法，该算法可以找到无向图中两个节点之间的最短路径，且成本是动态的。 所谓动态，我的意思是边缘成本取决于下一步( future )。 例如，在这样的图表中:
我正在寻找从“a”到“e”的最短路径，但“a”到“b”的成本取决于下一步。去c就是7，去d就是9。
我的问题是:是否有解决该问题的算法？
最佳答案
将问题简化为“常规”最短路径问题
创建虚拟顶点 b1、b2(而不是 b)和边:
(a,b1,7), (b1,c,6), (a,b2,9), (b2,d,5)
其余的边和顶点保持原样。
现在，运行从源到目标的常规最短路径算法 ( Dijkstra/Bellman Ford )。
(对任何“条件”权重边重复该过程)。
关于algorithm - 具有动态边成本的最短路径(算法)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22898180/