I'm working on LightOJ problem 1002 and I can see that the problem requires a variant of Dijkstra's algorithm. When I refer to books, however, they require a different type of PriorirtyQueue than what is included in Java's Collections library.
My question is, for those of you who have had to implement Dijkstra's in a contest or even from an OJ while practicing, have you had to write your own Heap and PriorityQueue implementation usually, or is there a quicker way? I've been told before that TreeSet could be used in replacement for PriorityQueue. I've tried to look around a bit for shortest path tagged problems and how people have used Dijkstra's here on Codeforces, but implementations seem to vary so drastically, and it makes it quite confusing to know which style to follow and study. Could someone show me an example of how they implement Dijkstra's algorithm for contests in Java. It would be really helpful to learn from and reference from. Thanks.
Why don't you just use JAVA's Priority Queue? It is implemented by a heap data structure which is fast enough. I wrote Dijkstra's algorithm several times in java, and you only need a PQ, nothing else.
Do you mean something else?
I found that
TreeSetis more fast thanPriorityQueue. So I would advise to useTreeSetfor Dijkstra. I cannot give real submissions here for comparison for now, but it seems that withPriorityQueueI've been getting TLE, while got AC when rewritten solution to useTreeSet.I suppose you are referring to an implementation of a priority queue with a decrease-key operation. Although the priority queue provided by the Java library does not support the decrease-key operation, you can nevertheless use it for Dijkstra's algorithm.
Suppose during Dijkstra's algorithm you found a smaller distance for the node
v. Then you simply don't update the distance for the pair(dist_val, v)in the priority queue, but instead insert a new pair(new_dist_val, v). Your priority queue now contains multiple pairs forv, but this is not a problem. Sincenew_dist_val < dist_val, the pair(new_dist_val, v)will be popped earlier from the priority queue than the pair(dist_val, v). Later, when you pop the pair(dist_val, v)you can recognize it as being old by comparingdist_valto the current distance ofv, i.e. ifdist_val != dist_array[v], you ignore the pair(dist_val, v).Here are two discussions on Stackoverflow on this topic:
Easiest way of using min priority queue with key update in C++
Why does Dijkstra's algorithm use decrease-key?
But doing so will increase the complexity from O(Elog(V)) to O(Elog(E)). As we can may end up inserting all the edges into our PriorityQueue.
$$$E \le V^2$$$, so $$$\log E \le 2 \log V$$$, which gives the same complexity (the constant factor shouldn't matter as much).
I didn't read the problem but a custom implementation could be useful to have indexing operations, you can see Indexed Priority Queue, you can read more here.