performance - 在具有节点和边权重的图中找到最短路径？

Question

假设我有一个加权图，边和顶点都有权重。如何找到从某个节点 s 到某个节点 t 的“最便宜”路径？我的复杂度应该是 O(n²(n+m)).

Answer 1

解决此问题的一种方法是将图转换为新图，其中仅对边加权，而不对顶点加权。为此，您可以将每个节点拆分为两个节点，如下所示。对于任意节点 v，创建两个新节点 v₁ 和 v₂。先前进入节点 v 的所有边现在都进入节点 v₁，所有离开节点 v 的边现在离开 v₂。然后，在 v₁ 和 v₂ 之间放置一条边，其代价是节点 v 的代价。

在这个新图中，从一个节点到另一个节点的路径成本对应于原始图中原始路径的成本，因为所有边权重仍然被支付并且所有节点权重现在都使用新插入的边缘。

构建此图的时间 O(m + n) 应该是可行的，因为您需要恰好更改每条边一次和每个节点恰好一次。从那里，您可以只使用普通的 Dijkstra 算法在时间 O(m + n log n) 中解决问题，给出 O(m + n log n) 的整体复杂性。如果存在负权重，则可以改用 Bellman-Ford 算法，总复杂度为 O(mn)。

希望这对您有所帮助!