动态边权最短路径算法

Question

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

我要找到从“a”到“e”的最短路径，但是“a”到“b”的成本取决于下一步。如果我去c，则为7；如果我去d，则为9。

我的问题是：是否有一种解决该问题的算法？

- trojek

Answer 1

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

创建虚拟顶点 b1 和 b2（替代 b），并添加以下边：

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

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

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

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

- amit

---

这个的时间复杂度是多少？难道不是指数级的吗？ - chrk

你可以将每条边替换为两条边。即使你连接多个连接，仍然可以通过添加线性数量的边来完成。 - amit

你知道其他的解决方案吗？ - trojek

@trojek 你可以完全绕过 b，并使用权重之和从 a 到 c 和 d 创建节点，但在一般情况下，我认为这更加复杂。 - amit

我曾经考虑过这个问题，但这不是一个好主意。在这种情况下，它可以工作，但如果你有更大更复杂的图形，使用“众所周知”的算法如Dijkstra来解决它将会遇到问题。 - trojek

Answer 2

正如之前的回答所提到的，由于边权只取决于路径中的下一个顶点，因此您可以复制每个顶点，最多复制|V|个，以跟踪下一个要访问的顶点，其中每个重复的顶点仅有一个出度邻居，并且出度成本取决于访问哪个邻居。在这个修改后的图上运行Dijkstra算法的总复杂度不会超过O(V(V log v + E))，如果每个顶点的边度数受到限制，则复杂度为O(k(V log V + E))，其中V是顶点数，E是边数。

- user2566092