algorithm - 具有动态边成本的最短路径(算法)

Question

我正在寻找一种算法，该算法可以找到无向图中两个节点之间的最短路径，且成本是动态的。所谓动态，我的意思是边缘成本取决于下一步( future )。例如，在这样的图表中:

我正在寻找从“a”到“e”的最短路径，但“a”到“b”的成本取决于下一步。去c就是7，去d就是9。

我的问题是:是否有解决该问题的算法？

Answer 1

将问题简化为“常规”最短路径问题

创建虚拟顶点 b1、b2(而不是 b)和边:

(a,b1,7), (b1,c,6), (a,b2,9), (b2,d,5)

其余的边和顶点保持原样。

现在，运行从源到目标的常规最短路径算法 ( Dijkstra/Bellman Ford )。

(对任何“条件”权重边重复该过程)。