具有动态边缘成本的最短路径（算法）

 

我正在寻找一种算法，可以找到无向图中两个节点之间的最短路径，其成本是动态的。 通过动态，我的意思是边缘成本取决于下一步（未来）的步骤。 例如，在这样的图表中：

动态边缘成本最短路径问题

我正在寻找从“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）。

（对任何“条件”权重边缘重复该过程）。

正如前面的答案所述，由于边权重仅取决于路径中的下一个顶点，因此可以使用最多的| V |来复制每个顶点。 跟踪哪个顶点下一个走过的副本，每个副本顶点只有一个传出邻居，传出成本取决于接下来访问哪个邻居。 在这个修改后的图上运行Dijkstra算法的总体复杂度不低于O（V（V log v + E）），并且如果在每个顶点上有有界的边缘度k，则复杂度为O（k（V log V + E）），其中V是顶点的数量，E是边的数量。

链接地址: http://www.djcxy.com/p/35219.html

上一篇: shortest path with dynamic edge cost (algorithm)

下一篇: pair shortest path algorithms work with negative weights?