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

Question

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

Answer 1

解决此问题的一种方法是将图转换为仅权重边缘而不是顶点的新图。为此，您可以按如下方式将每个节点分成两个节点。对于任何节点v，新建两个节点v1和v2。以前进入节点v的所有边现在都进入节点v1，离开节点v的所有边现在都离开v2。然后，在v1和v2之间放置一条边，其成本为节点v1的成本。

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

构造此图应该在时间O（m + n）内可行，因为您需要精确地更改每个边一次，并且每个节点只更改一次。从那里，您可以只使用普通的Dijkstra算法来解决时间为O（m + n log n）的问题，从而使总体复杂度为O（m + n log n）。如果存在负权重，则可以改用Bellman-Ford算法，得出总复杂度为O（mn）。

希望这可以帮助！