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

Question

这是一般算法问题.我想在无向图上运行一些最短路径算法,其中边和顶点都有与之相关的成本.大多数最短路径寻找算法都不考虑顶点成本.有没有办法来弥补这个问题？

Answer 1

通过将边缘连接到边缘的成本的两个顶点的成本加一半来增加图形(称为边缘的增加成本).

然后忽略顶点成本并在增强图上运行普通的最短路径算法.

对于每条路径

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

增量图中的成本是

(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增强图中的路径的成本是原始图中相同路径的成本减去起始顶点和结束顶点的组合成本的一半.

因此,路径是原始图中的最短路径,并且只有它是增强图中的最短路径.