Dijkstra算法属性

Question

Dijkstra(G,w,s) {
  ISS(G,s);
  let S be an empty set
  let Q be a priority queue, initialized with V[G]
  while Q is not Empty:
       u<-extractMin(Q);
       add u to S
       for each vertex v neighbor of u
             Relax(u,v,w);
}

我的问题是，在算法的 while 循环中为什么要选择 Q 中所有 v 的最小 d [v]，如果我们不选择最小值会发生什么？我觉得所有边缘 (u,v) 都会按照广度优先顺序进行放松（这意味着如果 s->u->v 且 (s,v) 不在 E，则 (s,u) 将在 (u,v) 之前被放松），那为什么每次都选择最小的 d[v] 是很重要的呢？

假设存在一个函数 extractMaxFiniteD(Q)，它返回在 Q 中具有有限的最大 d[v] 值的顶点 v。

假设我们将这行代码更改为 u<-extractMaxFiniteD(Q); 能否有人为我画出一张图，在修改后的算法中它会失败 - 或者更好的是 - 最短路径的哪个属性会受到侵犯？

我知道这个问题可能相当困难和抽象，但如果有人能帮我解答就太好了。

- Ofek Ron

---

你真的在任何图上尝试过吗？使用Max会产生错误结果的概率非常高！ - Armen Tsirunyan

我对特定的图表不太感兴趣，我想了解我们选择每一步最小化的属性是什么。 - Ofek Ron

如果你在几乎任何图表上逐步进行并查看中间结果，你就会理解min函数的目的。 - Armen Tsirunyan

选择无穷大是不合法的，当然了，假设extractMaxFiniteD返回顶点v，使得它在Q中具有最大的有限d[v]，那么这还是那么简单吗？ - Ofek Ron

Answer 1

Dijkstra算法的主要思想是：当你从Q中取出一个顶点时，这个顶点是好的。你不需要在将来松弛它。如果你随机从Q中取出一个元素，则此条件不成立 - 一旦你取出一个顶点v，不能保证d[v]确实是到v的最短路径。如果你取最小值 - 它是有保证的，因为如果v在Q中是最小的，则对于Q中的每个u，d[u]>=d[v]，因此无论你下一步做什么松弛操作 - 都不能改善d[v]。

- amit

Answer 2

例子：

节点：a，b，c
边缘（和权重）：（a，b，1）（a，c，10）（b，c，1）

在这个例子中运行你的算法。你会发现到c的最小成本路径是10，而显然是2。

当你从Q中删除一个节点时，你永远不会再次松弛它，如果你删除了一个最大成本的节点，那么你就不会考虑到达该节点的更便宜的方法。

如果你不想从Q中选择最小节点，那么也不能将其从Q中删除，必须将其保留在集合中，以便在将来的迭代中进行松弛。那基本上就是贝尔曼-福德算法所做的事情。

- yurib