这是一个消费税：
在某些图问题中，顶点可以有权重而不是
或者除了边的权重之外。设 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)
in (b) w(u,v) = 0（或 const），并且该解决方案也适合（c）！
The idea behind it is using an edge cost you the weight of the edge, and the cost of reaching the target vertice. The cost of the source was already paid, so you disregard it1.
减少问题，而不是改变算法，通常更容易使用、证明和分析！。
(1) 在这个解决方案中，您“错过”了源的权重，因此从s to t将：dijkstra(s,t,w') + vertex_weight(s)_ [where dijkstra(s,t,w')是距离s to t用出w'
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
