具有顶点和边缘成本的最短路径算法
这是一个通用算法问题。 我想在无向图上运行一些最短路径算法，其中边和顶点都有与其相关的成本。 大多数最短路径搜索算法不考虑顶点成本。 有什么方法可以弥补这个问题吗？
通过将边连接到边的成本的两个顶点的成本的一半加起来（称为边的增加成本）来增加图。
然后忽略顶点成本并在增广图上运行普通的最短路径算法。
对于每个路径
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之间的路径代价是原始图中相同路径的开销减去开始和结束顶点总成本的一半。
因此，路径是原始图中的最短路径，当且仅当它是增广图中的最短路径。
链接地址: http://www.djcxy.com/p/35251.html上一篇: Shortest path algorithm with both vertex and edge costs