具有顶点权重的最短路径
这是一个消费税：
在某些图形问题中，顶点可以具有权重而不是或者除了边的权重之外。 设Cv是顶点v的代价，C（x，y）是边（x，y）的代价。 该问题涉及在图G中找到顶点a和b之间最便宜的路径。路径的成本是路径上遇到的边和顶点的成本的总和。
（a）假设图中每条边的权重为零（而非边的成本为∞）。假设所有顶点1≤v≤n的Cv = 1（即所有顶点的成本相同） 。 给出一个有效的算法来查找从a到b的最便宜路径及其时间复杂度。
（b）现在假设顶点成本不是恒定的（但都是正的）并且边缘成本保持如上。 给出一个有效的算法来查找从a到b的最便宜路径及其时间复杂度。
（c）现在假设边缘和顶点成本不是恒定的（但都是正的）。 给出一个有效的算法来查找从a到b的最便宜路径及其时间复杂度。
这是我的答案：
（a）使用正常的BFS;
（b）使用dijkstra算法，但用顶点权重代替权重;
（C）
也使用dijkstra的算法
如果只考虑边缘权重，那么对于dijkstra算法的关键部分，我们有：
if (distance[y] > distance[v]+weight) {
distance[y] = distance[v]+weight; // weight is between v and y
}
现在，通过考虑顶点权重，我们有：
if (distance[y] > distance[v] + weight + vertexWeight[y]) {
distance[y] = distance[v] + weight + vertexWeight[y]; // weight is between v and y
}
我对吗？
我想我对（c）的回答太简单了，是吗？
你走在正确的轨道上，解决方案非常简单。
在B，C中，将问题简化为正常的dijkstra，它假定顶点没有权重。
为此，您需要定义w':E->R ，这是一个新的边权重函数。
w'(u,v) = w(u,v) + vertex_weight(v)
在（b）中w(u,v) = 0 （或const），并且该解对于（c）也是健壮的！
其背后的想法是使用边缘来减少边缘的重量，以及达到目标顶点的成本。 源代码的成本已经支付了，所以你不理会它1。
减少问题，而不是改变算法，通常使用，证明和分析要简单得多！
（1）在这个解决方案中，“错过”源的权重，所以从s到t的最短路径将是： dijkstra(s,t,w') + vertex_weight(s)_ [其中dijkstra(s,t,w')是从s到t的距离，用w'
顶点权重可以通过切割两个顶点a1和a2中的每个顶点a，a1和a2之间的权重为a来删除。
我认为你适合dijkstra算法的改编。
链接地址: http://www.djcxy.com/p/35249.html