2

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

  • DeleteMin（返回具有最小键的元素并将其从集合中删除。）

  • DecreaseKey（适应特定元素键值的减少）

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

1 回答 1

6

为什么使用 DeleteMin 来检索最小元素 - 为什么不是随机元素？

我们从开放顶点集中检索并删除最小元素，Q因为它确保了最小性（稍后在证明中使用）。没有它 - 无法保证最小化功能，并且解决方案不会是最佳的（不会是最短路径）。请记住，一旦我们找到通往 的路径v，我们会将其从 中删除Q，并且永远不会重新打开它，因此我们取出的边必须具有可用路径最小的边。

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

DecreaseKey 的目的是什么？在伪代码中，它总是在元素的值更改后调用。它在做什么？

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

于 2012-06-21T11:52:37.500 回答