证明Dijkstra算法提取的距离值是非递减的？
我正在回顾我的旧算法笔记并发现了这个证明。这是我的一项作业，我做对了，但我觉得肯定缺乏证据。
问题是证明 Dijkstra 算法中从优先级队列中取出的距离值是一个非递减序列。
我的证明如下：
反证法。握拳，假设 我们从 Q 中拉出一个顶点 d 值“i”。下次我们拉一个 d 值为“j”的顶点。当我们 拉我，我们已经敲定了 d 值并计算最短路径 从起始顶点 s 到 i。自从 我们有正边权重，它是 我们的 d 值不可能缩小 当我们向路径添加顶点时。如果 从 Q 中拉出 i 后，我们拉出 j 较小的 d 值，我们可能没有 到 i 的最短路径，因为我们可能是 能够通过j到达i。然而， 我们已经计算出最短的 通往岛的路径我们没有检查 可能的路径。我们不再有 保证路径。矛盾。
如何改进这个证明？或者更好的是，有不同的方法吗？它看起来很弱:)
编辑：抱歉，在这种情况下，我的优先级队列是用最小堆实现的
I'm reviewing my old algorithms notes and have come across this proof. It was from an assignment I had and I got it correct, but I feel that the proof certainly lacks.
The question is to prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.
My proof goes as follows:
Proof by contradiction. Fist, assume
that we pull a vertex from Q with
d-value 'i'. Next time, we pull a
vertex with d-value 'j'. When we
pulled i, we have finalised our
d-value and computed the shortest-path
from the start vertex, s, to i. Since
we have positive edge weights, it is
impossible for our d-values to shrink
as we add vertices to our path. If
after pulling i from Q, we pull j with
a smaller d-value, we may not have a
shortest path to i, since we may be
able to reach i through j. However,
we have already computed the shortest
path to i. We did not check a
possible path. We no longer have a
guaranteed path. Contradiction.
How could this proof be improved upon? Or better yet, is there a different approach? It just seems pretty weak :)
Edit: Sorry, in this case my priority queue is implemented with a Min-heap
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
让我们建立这些（这些都是正确的，因为它们基本上是算法的定义）：
继续 (1)，假设 (2) 适用，该出列节点的 d 值将至少等于先前提取的 d 值，因为每个节点的 d 值取决于节点的 d 值在它之前出列，这是一种递归定义。由于 (3) 和 (4) 是正确的，因此该递归定义在 d 值为 0 的起始节点处结束。
因此，如果每个节点的 d 值至少等于其之前的 d 值，并且 (1) 仍然适用，则从优先级队列中提取的 d 值集合非递减。
（读完这篇文章和你写的内容后，基本上是一样的，但我认为呈现得更好一些）
Let's establish these (these are all true, since they are, basically, the definition of the algorithm) :
Continuing (1), the d-value of that dequeued node, assuming (2) applies, will be at the very least equal to the previous d-value extracted, since each node's d-value depends on the d-values of the nodes dequeued prior to it, which is a sort of recursive definition. Since (3) and (4) are correct, this recursive definition ends at the starting node which has d-value of 0.
So, if each node's d-value is at the very least equal to the d-value before him, and (1) still applies, the set of d-values extracted from the priority queue is non-decreasing.
(After reading through this, and what you wrote, it's basically the same, but presented a bit better I think)