Shortest path algorithm with both vertex and edge costs

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.

For each path

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))

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.

链接地址: http://www.djcxy.com/p/35252.html

上一篇: 在具有特定成本的无向图中查找路径

下一篇: 具有顶点和边缘成本的最短路径算法