为什么Dijkstra的算法使用减少键？

Question

为什么Dijkstra的算法使用减少键？

wee*_*eeb 88 algorithm dijkstra priority-queue graph-algorithm data-structures

Dijkstra的算法教给我如下

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

Run Code Online (Sandbox Code Playgroud)

但是我一直在阅读关于算法的一些阅读,我看到的很多版本都使用了reduce-key而不是insert.

为什么会这样,这两种方法之间有什么区别？

Answer 1

tem*_*def 65

之所以使用减少键而不是重新插入节点是保持节点的数量在优先队列小,从而降低优先级队列的总数目从队列中取出小和每个优先级队列的平衡低的成本.

在Dijkstra算法的实现中,该算法将节点以其新优先级重新插入优先级队列,将一个节点添加到图中每个m个边缘的优先级队列中.这意味着,有对优先级队列米入队操作和米出队操作,得到的O总运行时间(米Ť _Ë +米Ť _d),其中T _ë是入队到优先级队列所需要的时间,T _d是从优先级队列中出队所需的时间.

在支持reduce-key的Dijkstra算法的实现中,保存节点的优先级队列以其中的n个节点开始,并且在算法的每个步骤中移除一个节点.这意味着堆出队的总数是n.对于通向它的每个边缘,每个节点都会有一个为其调用的减少键,因此减少键的总数最多为m.这给出了运行时间(n T _e + n T _d + m T _k),其中T _k是调用减小键所需的时间.

那么这对运行时有什么影响？这取决于您使用的优先级队列.这是一个快速表,显示不同优先级队列和不同Dijkstra算法实现的总体运行时间:

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

Run Code Online (Sandbox Code Playgroud)

正如您所看到的,对于大多数类型的优先级队列,渐近运行时确实没有区别,而减少键的版本不太可能做得更好.但是,如果使用优先级队列的Fibonacci堆实现,那么在使用reduce-key时,Dijkstra的算法确实会渐进地提高效率.

简而言之,使用减少键和优先级优先级队列,可以使Dijkstra的渐近运行时间超出可能的范围,如果你继续进行排队和出队.

除此之外,一些更先进的算法,如Gabow的最短路径算法,使用Dijkstra算法作为子程序,并严重依赖于减少键实现.他们使用的事实是,如果您事先知道有效距离的范围,则可以基于该事实构建超高效优先级队列.

希望这可以帮助!

+1：我忘记考虑堆了。有一点狡辩，由于插入版本的堆每条边都有一个节点，即 O(m)，那么它的访问时间不应该是 O( log m )，从而使总运行时间为 O( m log m ) 吗？我的意思是，在普通图中，m 不大于 n^2，因此这会减少到 O( m log n )，但在两个节点可能由不同权重的多个边连接的图中，m 是无界的（当然，我们可以声称两个节点之间的最小路径仅使用最小边，并将其简化为普通图，但对于随机数来说，这很有趣）。 (2认同)
@ rampion-的确有一点，但由于我认为通常会假设在触发算法之前已减少了平行边，所以我认为O（log n）与O（log m）无关紧要。通常假定m为O（n ^ 2）。 (2认同)
如果您在探索图表时以不同的优先级重新插入节点，那么堆大小将为 O(m)，这是正确的。你也是对的，O(log m) = O(log n)，因为 log n <= log m <= 2log n。惯例是在写出渐近符号时使用 log n 而不是 log m，并且由于 O(m log m) = O(m log n) 我们通常使用后者，但 O(m log m) 在技术上仍然是正确的。 (2认同)

Answer 2

Mar*_*ton 25

2007年,有一篇论文研究了使用reduce-key版本和插入版本之间执行时间的差异.见http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

他们的基本结论是不使用减少键来表示大多数图表.特别是对于稀疏图,非减少键明显快于减少键版本.有关详细信息,请参阅该文章.

http://www.cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf是该论文的工作链接. (6认同)
警告：链接的论文中存在错误。第 16 页，函数 B.2：“if k < d[u]”应为“if k <= d[u]”。 (3认同)

归档时间：	13 年，7 月前
查看次数：	23360 次
最近记录：	5 年，11 月前