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

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增强图中的路径成本是原始图中相同路径的成本减去起点和终点的总成本的一半。

因此，一条路径是原始图中的最短路径当且仅它是增广图中的最短路径。