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

这是一个通用算法问题。我想在无向图上运行一些最短路径算法，其中边和顶点都有与其相关的成本。大多数最短路径搜索算法不考虑顶点成本。有什么方法可以弥补这个问题吗？具有顶点和边缘成本的最短路径算法

来源

2012-12-31 fatma.ekici

对于每个边，将相应顶点的一半成本添加到边成本，然后忽略顶点成本。 –

它不会夸大顶点的成本吗？如果一个顶点有4个连接到它的边，则该顶点的成本将被添加2次。 –

看看Prim的算法。 – user1929959

通过将边缘连接到边缘的两个顶点的成本的一半加起来（称为边缘的增加成本）来增加图形。

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

对于每个路径

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之间的路径的成本是相同的成本原始图中的路径减去开始和结束顶点的总成本的一半。

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

来源

2012-12-31 21:41:04

+1为优雅的解决方案。 –

+1真的很棒！ – Chasefornone

在S. Skiena的算法设计手册中提到，如果给出一个图的权重位于顶点而不是边的图，我们可以将有向边（i，j）的代价视为顶点的代价学家然后，通过运行Dijkstra算法解决问题我们是否可以在这个问题中采用相同的方法？我不清楚为什么我们应该增加每个顶点的一半成本。 –

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

回答

相关问题