algorithm - 为什么 Dijkstra 的算法需要使用 deleteMin() 和 decreaseKey()？

Question

在大多数伪代码中，我通常会发现以下内容:

• DeleteMin (Return the element with the smallest key and delete it from the set.)

• DecreaseKey (Accomodate the decrease in key value of a particular element)

• 为什么使用 DeleteMin 来检索最小元素 - 为什么不是随机元素？
• DecreaseKey 的用途是什么？在伪代码中，它总是在元素值更改后调用。它在做什么？

Answer 1

Why is DeleteMin being used to retrieve the smallest element- why not a random one?

我们从 Q 中检索并删除最小元素的集合 打开顶点，因为它确保了最小性(稍后在证明中使用)。 没有它 - 最小性特征得不到保证，解决方案将不是最优的(不会是最短路径)。请记住，一旦我们找到了 v 的路径，我们将其从 Q 中删除，并且永远不会重新打开它，所以我们取出的边缘必须具有可用路径最小的边缘。

请注意，对于这个(最小的)顶点，让它成为 v :对于每个 u在Q d(u) + x <= d(v) - 因为当没有负边时使用 dijkstra 算法，x >=0。
对于任何其他顶点 - 这不是最小的 - 我们不能保证没有更短的路径尚未被发现。

What is the purpose of DecreaseKey? In pseudocode it's always called after the value of an element is changed. What is it doing?

使用减少是因为我们可能已经找到了一条新的、更好的路径到连接到我们找到的最后一个顶点的顶点。 这一步是 dijkstra 算法正在执行的松弛步骤。请记住，dijkstra 算法始终保持到每个顶点为止找到的最短路径，因为最后一步可能已经找到到某个顶点的新最短路径 -这一步是更新目前找到的最短路径。