w0ws0d0gg0's blog

Dijkstra's Algorithm in Java without a custom Heap/PriorityQueue? LightOJ Problem
By w0ws0d0gg0, history, 9 years ago, In English

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.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I found that TreeSet is more fast than PriorityQueue. So I would advise to use TreeSet for Dijkstra. I cannot give real submissions here for comparison for now, but it seems that with PriorityQueue I've been getting TLE, while got AC when rewritten solution to use TreeSet.

    → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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 for v, but this is not a problem. Since new_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 comparing dist_val to the current distance of v, i.e. if dist_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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      $$$E \le V^2$$$, so $$$\log E \le 2 \log V$$$, which gives the same complexity (the constant factor shouldn't matter as much).

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply