这是一个消费税:
在某些图形问题中,顶点可以具有权重,而不是边缘权重或者与边缘权重相加.设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)的回答太简单了,是吗？