让我们说我有一个加权图上两个边和顶点权重。如何找到最便宜的路径从某个节点s到一定的结点？我的复杂性应为O（n 2 （N + M））。

Let's say I have a weighted graph with weights on both edges and vertices. How do I find the "cheapest" path from a certain node s to a certain node t? My complexity should be O(n2(n+m)).

推荐答案

要解决，这将是图形转换成其中仅边缘加权，而不是顶点一个新的图的一种方法。要做到这一点，你可以拆开分成各个节点到两个节点如下。对于任何节点U，使两个新节点，v1和v2。所有的边缘了previously进入节点U现在进入节点V1，和叶子节点v所有边缘现在离开V2。然后，把v1和v2，其成本为节点V1的成本之间的边缘。

One way to solve this would be to convert the graph into a new graph in which only edges are weighted, not vertices. To do this, you can split each node apart into two nodes as follows. For any node v, make two new nodes, v1 and v2. All edges that previously entered node v now enter node v1, and all edges that leave node v now leave v2. Then, put an edge between v1 and v2 whose cost is the cost of node v1.

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

In this new graph, the cost of a path from one node to another corresponds to the cost of the original path in the original graph, since all edge weights are still paid and all node weights are now paid using the newly-inserted edges.

构建这个图应该是可行的时间为O（M + N），因为你需要改变每条边恰好一次，每个节点一次。从那里，你可以使用普通的Dijkstra算法解决时间为O问题（M + N log n）的，给人一种整体的复杂性为O（M + N log n）的。如果负权重存在，那么你可以使用Bellman-Ford算法​​来代替，给O（MN）的总复杂。

Constructing this graph should be doable in time O(m + n), since you need to change each edge exactly once and each node exactly once. From there, you can just use a normal Dijkstra's algorithm to solve the problem in time O(m + n log n), giving an overall complexity of O(m + n log n). If negative weights exist, then you can use the Bellman-Ford algorithm instead, giving a total complexity of O(mn).

希望这有助于！