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

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)

但是我已经做了一些关于算法的阅读，我看到的许多版本使用了递减键，而不是插入。

为什么会这样，这两种方法的区别是什么？

31794 次浏览
小开
最佳答案

The reason for using decrease-key rather than reinserting nodes is to keep the number of nodes in the priority queue small, thus keeping the total number of priority queue dequeues small and the cost of each priority queue balance low.

In an implementation of Dijkstra's algorithm that reinserts nodes into the priority queue with their new priorities, one node is added to the priority queue for each of the m edges in the graph. This means that there are m enqueue operations and m dequeue operations on the priority queue, giving a total runtime of O(m Te + m Td), where Te is the time required to enqueue into the priority queue and Td is the time required to dequeue from the priority queue.

In an implementation of Dijkstra's algorithm that supports decrease-key, the priority queue holding the nodes begins with n nodes in it and on each step of the algorithm removes one node. This means that the total number of heap dequeues is n. Each node will have decrease-key called on it potentially once for each edge leading into it, so the total number of decrease-keys done is at most m. This gives a runtime of (n Te + n Td + m Tk), where Tk is the time required to call decrease-key.

So what effect does this have on the runtime? That depends on what priority queue you use. Here's a quick table that shows off different priority queues and the overall runtimes of the different Dijkstra's algorithm implementations:

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)

As you can see, with most types of priority queues, there really isn't a difference in the asymptotic runtime, and the decrease-key version isn't likely to do much better. However, if you use a Fibonacci heap implementation of the priority queue, then indeed Dijkstra's algorithm will be asymptotically more efficient when using decrease-key.

In short, using decrease-key, plus a good priority queue, can drop the asymptotic runtime of Dijkstra's beyond what's possible if you keep doing enqueues and dequeues.

Besides this point, some more advanced algorithms, such as Gabow's Shortest Paths Algorithm, use Dijkstra's algorithm as a subroutine and rely heavily on the decrease-key implementation. They use the fact that if you know the range of valid distances in advance, you can build a super efficient priority queue based on that fact.

Hope this helps!

小开

In 2007, there was a paper that studied the differences in execution time between using the decrease-key version and the insert version. See http://www.cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf

Their basic conclusion was not to use the decrease-key for most graphs. Especially for sparse graphs, the non-decrease key is significantly faster than the decrease-key version. See the paper for more details.

小开

There are two ways to implement Dijkstra: one uses a heap that supports decrease-key and another a heap that doesn't support that.

They are both valid in general, but the latter is usually preferred. In the following I'll use 'm' to denote the number of edges and 'n' to denote the number of vertices of our graph:

If you want the best possible worst-case complexity, you would go with a Fibonacci heap that supports decrease-key: you'll get a nice O(m + nlogn).

If you care about the average case, you could use a Binary heap as well: you'll get O(m + nlog(m/n)logn). Proof is here, pages 99/100. If the graph is dense (m >> n), both this one and the previous tend to O(m).

If you want to know what happens if you run them on real graphs, you could check this paper, as Mark Meketon suggested in his answer.

What the experiments results will show is that a "simpler" heap will give the best results in most cases.

In fact, among the implementations that use a decrease-key, Dijkstra performs better when using a simple Binary heap or a Pairing heap than when it uses a Fibonacci heap. This is because Fibonacci heaps involve larger constant factors and the actual number of decrease-key operations tends to be much smaller than what the worst case predicts.

For similar reasons, a heap that doesn't have to support a decrease-key operation, has even less constant factors and actually performs best. Especially if the graph is sparse.


提交答案