21

这是一个消费税：

在某些图问题中，顶点可以有权重来代替或除了边的权重之外。令 Cv 为顶点 v 的成本，C(x,y) 为边 (x,y) 的成本。这个问题涉及在图 G 中找到顶点 a 和 b 之间的最便宜的路径。路径的成本是路径上遇到的边和顶点的成本之和。

(a) 假设图中每条边的权重为零（而非边的成本为∞）。假设所有顶点的Cv =1 1≤v≤n（即所有顶点的成本相同） . 给出一个有效的算法来找到从 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) 的回答太简单了，是吗？

4

2 回答 2

19

您走在正确的轨道上，解决方案非常简单。

在 B、C 中，将问题简化为正常的 dijkstra，它假定顶点上没有权重。
为此，您需要w':E->R为边定义一个新的权重函数。

w'(u,v) = w(u,v) + vertex_weight(v)

在 (b) w(u,v) = 0(或 const) 中，并且该解决方案对于拟合 (c) 也是稳健的！

其背后的想法是使用边缘会消耗边缘的权重以及到达目标顶点的成本。源的成本已经支付，所以你忽略它1。

减少问题，而不是更改算法，通常更易于使用、证明和分析！

s(1) 在此解决方案中，您“错过”了源的权重，因此从to的最短路径t将是：dijkstra(s,t,w') + vertex_weight(s)_[where dijkstra(s,t,w')is the distance from sto tusing outw'

于 2012-05-04T17:06:23.800 回答
4

可以通过将两个顶点 a1 和 a2 中的每个顶点 a 以 a1 到 a2 的边以 a 的权重切片来去除顶点权重。

我认为你适合dijkstra算法的改编。

于 2012-05-04T17:13:07.620 回答