fdh*_*fdh 2 language-agnostic algorithm computer-science dijkstra
在大多数伪代码中,我通常会发现以下内容:
DeleteMin(返回具有最小键的元素并将其从集合中删除.)
DecreaseKey(适应特定元素键值的减少)
为什么使用DeleteMin来检索最小元素 - 为什么不是随机元素？
我们从Q开放顶点集合中检索和删除min元素,因为它确保了最小化(后来在证明中使用).没有它 - 无法保证最小化功能,并且解决方案将不是最佳的(不会是最短路径).请记住,一旦我们找到了路径v,我们将其从中移除Q,并且永远不会重新打开它,因此我们取出的边缘必须具有可用路径最小的边缘.
注意,对于此(最小)顶点,让它成为v:对于每个u在Q d(u) + x <= d(v)-因为当没有负边缘中,x> = 0 Dijkstra算法被使用.
对于任何其他顶点 - 这不是最小的 - 我们不能保证没有更短的路径可供发现.
DecreaseKey的目的是什么？在伪代码中,它总是在元素的值改变之后调用.它在做什么？
使用减少是因为我们可能找到了一条新的,更好的路径,这些路径连接到我们找到的最后一个顶点.这一步是dijkstra算法正在制定的放松步骤.请记住,Dijkstra算法一直保持至今每个顶点发现的最短路径,因为最后一步可能已经找到了新的最短路径一些顶点-这一步更新迄今为止发现的最短路径.