graph - 具有顶点权重的最短路径

Question

这是一个消费税:

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

Answer 1

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

在B,C中,将问题减少到正常的dijkstra,它假设顶点没有权重.
为此,您需要w':E->R为边缘定义一个新的权重函数.

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

在(b)w(u,v) = 0(或const)中,解决方案也很健壮,以适应(c)!

它背后的想法是使用边缘成本边缘的权重,以及到达目标顶点的成本.源的成本已经支付,所以你忽略它¹.

减少问题而不是改变算法通常更容易使用,证明和分析!

(1)在该溶液中你"错过"该源的重量,所以从最短路径s来t将是:dijkstra(s,t,w') + vertex_weight(s)_[其中dijkstra(s,t,w')是从距离s到t使用了w'

Answer 2

可以通过将每个顶点 a 分割为两个顶点 a1 和 a2 来去除顶点权重，并且边从 a1 到 a2 具有 a 的权重。

\n\n

我认为你对 dijkstra\xe2\x80\x99s 算法的改编是正确的。

\n