这是一个普遍的算法问题。我想在一个无向图，其中两个边和顶点具有与其相关的成本运行一些最短路径算法。大多数的最短路径寻找算法没有考​​虑顶点的成本考虑在内。有没有什么方法来弥补这个问题呢？

This is a general algorithm question. I want to run some shortest path algorithm on an undirected graph where both edges and vertices have costs associated with them. Most of the shortest path finding algorithms do not take the vertex costs into account. Is there any method to compensate this problem?

推荐答案

增广图表通过将两个顶点的边缘连接到边的成本的一半的成本（称之为边缘的增强成本）。

Augment the graph by adding half the cost of the two vertices an edge connects to the cost of the edge (call that the augmented cost of the edge).

则忽略顶点成本，对增强图形运行一个普通的最短路径算法。

Then ignore the vertex costs and run an ordinary shortest path algorithm on the augmented graph.

对于每个路径

v_0 -e_1-> v_1 -e_2-> v_2 -e_2-> ... -e_n-> v_n

成本的增加图为

the cost in the augmented graph is

(1/2*C(v_0) + C(e_1) + 1/2*C(v_1)) + (1/2*C(v_1) + C(e_2) + 1/2*C(v_2)) + ... + (1/2*C(v_(n-1)) + C(e_n) + 1/2*C(v_n))
= C(v_0) + C(e_1) + C(v_1) + C(e_2) + ... + C(e_n) + C(v_n) - 1/2*(C(v_0 + C(v_n))

因此​​两个顶点之间的路径成本 A 和 B 的增强图形是的费用相同的路径中的原始图形减去的开始和结束顶点的一半结合成本

so the cost of a path between two vertices a and b in the augmented graph is the cost of the same path in the original graph minus half the combined cost of the start and end vertices.

因此​​，一个路径是在原始图中的最短路径，当且仅是在增强图形的最短路径。

Thus a path is a shortest path in the original graph if and only it is a shortest path in the augmented graph.