2

我正在查看我的旧算法笔记并遇到了这个证明。这是我的一个作业，我做对了，但我觉得证明确实缺乏。

问题是prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

我的证明如下：

反证法。首先，假设我们从 Q 中拉出一个 d 值为“i”的顶点。下一次，我们拉出一个 d 值为 'j' 的顶点。当我们拉出 i 时，我们已经确定了我们的 d 值并计算了从起始顶点 s 到 i 的最短路径。因为我们有正的边权重，所以当我们向路径添加顶点时，我们的 d 值不可能缩小。如果从 Q 中拉出 i 后，我们拉出具有较小 d 值的 j，我们可能没有到 i 的最短路径，因为我们可能能够通过 j 到达 i。但是，我们已经计算了到 i 的最短路径。我们没有检查可能的路径。我们不再有保证的路径。矛盾。

如何改进这个证明？或者更好的是，有不同的方法吗？它似乎很弱:)

编辑：对不起，在这种情况下，我的优先级队列是用最小堆实现的

4

1 回答 1

1

让我们建立这些（这些都是真的，因为它们基本上是算法的定义）：

  1. Dijkstra 算法中的优先级队列将在算法的每次迭代中为您提供具有最低 d 值的节点。
  2. 没有负边权重。
  3. 一旦节点出队，它将永远不会返回队列。
  4. 已经出队的节点的 d 值是最终的，并且从那时起不会改变。

继续（1），假设（2）适用，该出队节点的 d 值将至少等于提取的前一个 d 值，因为每个节点的 d 值取决于节点的 d 值在它之前出列，这是一种递归定义。由于 (3) 和 (4) 是正确的，因此该递归定义在 d 值为 0 的起始节点处结束。
因此，如果每个节点的 d 值至少等于他之前的 d 值，并且(1) 仍然适用，从优先级队列中提取的 d 值集合是非递减的。

（看完这篇，和你写的，基本上是一样的，但我认为呈现得更好一些）

于 2010-04-14T15:06:36.823 回答