Why does Dijkstra's algorithm use decrease-key?

Question

Dijkstra's algorithm was taught to me was as follows

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)

But I've been doing some reading regarding the algorithm, and a lot of versions I see use decrease-key as opposed to insert.

Why is this, and what are the differences between the two approaches?

Solution 1

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 T_e + m T_d), where T_e is the time required to enqueue into the priority queue and T_d 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 T_e + n T_d + m T_k), where T_k 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!

Solution 2

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.

Solution 3

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.

Comments

[templatetypedef]

Downvoter- Can you please explain what's wrong with this question? I think it's perfectly fair, and many people (including me) were first introduced to the OP's version of Dijkstra's rather than the decrease-key version.

[rampion]

+1: I'd forgotten to account for the heap. One quibble, since the insert version's heap has a node per edge, ie O(m), shouldn't its access times be O( log m ), giving a total run time of O( m log m )? I mean, in a normal graph m is no greater than n^2, so this reduces to O( m log n ), but in a graph where two nodes may be joined by multiple edges of different weights, m is unbounded ( of course, we can claim that the minimum path between two nodes only uses minimal edges, and reduce this to a normal graph, but for the nonce, it's interesting).

[templatetypedef]

@rampion- You do have a point, but since I think it's generally assumed that parallel edges have been reduced prior to firing up the algorithm I don't think that the O(log n) versus O(log m) will matter much. Usually m is assumed to be O(n^2).

[graffe]

cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf‎ is a working link for that paper.

[Xeverous]

WARNING: there is a bug in the linked paper. Page 16, function B.2: if k < d[u] should be if k <= d[u].

[Justin]

@templatetypedef If we insert (distance, node) pairs into the (binary) heap instead of using decrease-key, it seems possible for the heap to grow to a size that is greater than the # of nodes n. In the worst case, we have to explore all edges (# of edges = m), so the heap will grow to O(m) which means each heap insert is O(logm). Exploring all edges therefore has a complexity of O(mlogm)?! I'm imagining a very simple DAG with n nodes and ~n^2=m edges. In this case, like rampion's case, it reduces to O(m log n^2) ~ O(m log n), but I am not sure about my previous logic. Is it correct?

[Justin]

I just learned that O(logE) is equivalent to O(logV): stackoverflow.com/a/65961472/1810877. So O(m log n) as written in the post is equivalent to the O(m log m) I had in mind. Still I am not sure if my belief that the heap can grow to a size m = # of edges is correct. This implies to me that the complexity is O(m log m)

[templatetypedef]

You are correct that the heap size will be O(m) if you reinsert nodes at different priorities when exploring the graph. You are also right that O(log m) = O(log n), since log n <= log m <= 2log n. The convention is to use log n rather than log m when writing out asymptotic notation, and since O(m log m) = O(m log n) we typically use the latter, but O(m log m) would still be technically correct.

[Justin]

Thank you @templatetypedef. I am looking at this optimization here: stackoverflow.com/a/60084732/1810877 (I am seeking clarification on it in the comments; your input is also welcome!). With this small optimization, I still think the complexity is ~O(m log n). There are still the same number of insertions but the number of dequeues is reduced. The former sets the upper bound on the complexity; therefore, it is still O(m log n).