我正在复习我的旧算法笔记，并且遇到了这个证明。这是我的一项作业，我做对了，但我觉得证据确实不足。
题目是证明Dijkstra算法中从优先级队列中取出的距离值是一个非递减序列。
我的证明如下:
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.
如何改进这个证明？或者更好的是，是否有不同的方法？它看起来很弱:)
编辑:抱歉，在这种情况下我的优先级队列是用最小堆实现的
最佳答案
让我们建立这些(这些都是真的，因为它们基本上是算法的定义):
- The Priority Queue in Dijkstra's algorithm will give you the node with the lowest d-value in each iteration of the algorithm.
- There are no negative edge weights.
- Once a node has been dequeued, it will never return to the queue.
- The d-value of a node that has been dequeued is final, and will not change from that point on.
继续 (1)，假设 (2) 适用，该出队节点的 d 值将至少等于先前提取的 d 值，因为每个节点的 d 值取决于 d 值在它之前出队的节点的数量，这是一种递归定义。由于 (3) 和 (4) 是正确的，这个递归定义结束于 d 值为 0 的起始节点。
因此，如果每个节点的 d 值至少等于他之前的 d 值，并且 (1) 仍然适用，则从优先级队列中提取的 d 值集是非递减.
(看完这个和你写的，基本一样，但我觉得表现得更好一点)
关于algorithm - 证明 Dijkstra 算法中提取的距离值是非递减的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2634460/