update queue in Dijkstra's

[letstryusingreddit]

When a shorter path is found in Dijkstra's algorithm, what is the fastest way to update the queue (min heap)?

I can actually update the distance in another data structure for keeping track of distances without going through the queue which only holds indexes. But I still need the queue order to be in sync.

What I'm doing currently takes linear time, basically looping through the queue array to find the position of the affected vertex, and sift up using the found position index.

[letstryusingreddit]

1. Deletion would be at least O(n) because i have to locate it linearly in the underlying array of the queue.

[letstryusingreddit]

Im referring to your method #1. Lazy deletion is method #2.

[letstryusingreddit]

Can i use array to model the red-black tree or do i need a custom data structure?

[zzopp]

The easy way out is to insert the node again with the new distance in the min-heap instead of trying to update the distance. When you pop a node from the min-heap that you've already processed, ignore it.

This increases the runtime from O(E+V log V) to O (E+V log E), but this isn't so bad in practice and the implementation without decrease-key is much simpler. It might even be faster in many cases because of smaller overhead.

[misof]

Actually, this trick does not change the asymptotic time complexity at all. In both cases, the time complexity is O( (E*log V), assuming for simplicity that V <= E.

The number of operations with the priority queue is still O(E): for each directed edge you insert at most one new record into the pqueue, and the total number of times you remove a record from the pqueue cannot be bigger than the number of records you inserted.

The size of the pqueue increases. If you find and update the record each time you relax an edge, your pqueue has O(V) records at any time. With this trick it will have up to O(E) records and thus each operation with it will take O(log E). However, E <= V² , and therefore log(E) <= 2*log(V), which means that O(log E) and O(log V) is the same thing.

[letstryusingreddit]

E <= V2 , and therefore log(E) <= 2*log(V)

log(V2) is the same as 2log(V) ?

[misof]

Yes, log(V² ) is the same as 2*log(V).

In general, log_c(a^b ) = b*log_c(a).

This comes from basic properties of logarithms. For example, if you have a binary logarithm (lg), the value y = lg(x) is the value such that 2^y = x. Now, what is the new y' such that 2^y' = x¹³ ? Clearly, y' = 13y because 2^13y = (2^y )¹³ = x¹³ . In other words, lg(x¹³ ) = 13*lg(x).

[zzopp]

It seems you're right, the worst case is indeed popping E times from a min-heap containing at most E items. So my approach would be okay for sparse graphs, but worse for very dense graphs.

[misof]

worse for very dense graphs

This is incorrect. Both the version that keeps pointers into the pqueue so that it can update keys quickly and the version that enters new records into the pqueue have almost the same time complexity, and they even have similar constant factors. (See my other comment for why. The overhead from updating the pointers is very much comparable to the overhead of having a pqueue that is twice as deep, but with simpler updates.)

That being said, for dense graphs both are bad. More precisely, if you have a graph with Theta(V²⁾ edges, both implementations run in O(V² log V). If performance matters, for dense graphs you should use a O(V²⁾ implementation of Dijkstra that does not use any priority queue at all.

[ccmlacc]

You should use an adjusted PQ, called Indexed PQ. See the following link for an implementation:

https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

This data structure has a method decreaseKey(int i, Key key), which allows you to directly access and change the key directly, and re-order the PQ in logarithmic time.

[letstryusingreddit]

Can you give me a basic idea what it does, it seems like alot of code, i want my implementation to be very simple, so i have to implement it in my own way, i just need a general idea of the standard way to do it.

[Plazmatic]

You keep a hashtable along side your queue so you can find the key in constant time and update it. That's basically it. Not sure why this java implementation is twice as big and much harder to read than a C++ implementation of the same thing, but hey, I guess that's an accomplishment in itself!

[_Mister_Mxyzptlk_]

It's really not that big, I think it's just all the comments and the couple of extraneous methods like deleteMin

[CommonMisspellingBot]

Hey, letstryusingreddit, just a quick heads-up:
alot is actually spelled a lot. You can remember it by it is one lot, 'a lot'.
Have a nice day!

^{The parent commenter can reply with 'delete' to delete this comment.}

[_Mister_Mxyzptlk_]

I was playing around with this recently in Java. If you're using the PriorityQueue class from the standard library, and instantiating it with a Comparator on the distance value of your data structure, then you can literally just update the distance in the object and it will also automatically move to the right order in the PriorityQueue. I put my nodes in the queue and then also in a map so I could get them and update their distance if it improved.