图 - 带顶点权重的最短路径

Question

(c) 如果只考虑边权重，则可以使用 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）来说太简单了，是吗？

---

- Jackson Tale

Answer 1

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

在B和C中，将问题简化为普通的dijkstra算法，假设顶点没有权重。
为此，您需要定义w':E->R，即边的新权重函数。

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

在(b)中，w(u,v) = 0（或常数），并且该解决方案对于适合(c)也很稳健！

其背后的思想是使用边缘成本和到达目标顶点的成本来计算边缘权重。源的成本已经支付，因此可以忽略它¹。

简化问题而不是更改算法通常更容易使用、证明和分析！。

---

(1) 在这个解决方案中，您“错过”了源的权重，所以从s到t的最短路径将是：dijkstra(s,t,w') + vertex_weight(s)_ [其中dijkstra(s,t,w')是使用w'的从s到t的距离]

- amit

---

抱歉，我刚看到你说“在a、b中都使用reduce...转换成普通的Dijkstra算法”。我以为我的(a)有问题。:D感谢澄清。 - Jackson Tale

此外，“减少问题而不是改变算法通常更简单易用、易证明和分析！”这句话非常鼓舞人心！ - Jackson Tale

@zengr：对于原图中的每条无向边 (u,v)，在新图中添加两条边：(u,v)，使得 w'(u,v)=w(v) 和 (v,u)，使得 w'(v,u)=w(u)。给定这个新图 - 运行 Dijkstra 算法，并获取原图中的最短路径。 - amit

@zengr 你能找到的最短路径是s->u1->u2->...->un，它将给你总权重为w'(s,u1) + ... + w'(un-1,un) = w(s,u1) + w(u1) + w(u1,u2) + w(u2) + ... + w(un-1,un) + w(un)。在路径中不计算第一个节点的权重，因此可以在后处理期间轻松添加它。这不会影响正确性，因为G'中的所有路径都缺少相同的因子。 - amit

也许你可以在回答中指出，如果输入的图是无向的（我认为这里是这种情况），那么边需要“加倍”？无论如何，避免将(b)和(c)转换为具有两倍边数的有向图的一个技巧是使每条边的权重成为其端点顶点权重的总和：现在每个a-b路径的权重（几乎）翻倍了 ;) （您可以通过将a上的每条边的权重增加w(a)，并对b执行类似操作，使其完全加倍，尽管这不会影响找到的解决方案所发现的所有简单a-b路径都会以相同的数量更改。） - j_random_hacker

Answer 2

将每个顶点a分成两个顶点a1和a2，通过从a1到a2的边来切除顶点权重，权重为a的权重。

我认为您对Dijkstra算法的适应是正确的。

- Thomash

---

我认为这不会起作用。如果a与b、c和d相邻，那么a1和a2将与谁相邻？ - Christian Long