0

I found this implementation (relevant part follows) of Dijkstra using priority queue. Is it possible to speed it up further by implement Fibonacci heaps or even moving to Iterative Deepening A*?

 47     public static void computePaths(Vertex source)
 48     {
 49         source.minDistance = 0.;
 50         PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
 51     vertexQueue.add(source);
 52 
 53     while (!vertexQueue.isEmpty()) {
 54         Vertex u = vertexQueue.poll();
 55 
 56             // Visit each edge exiting u
 57             for (Edge e : u.adjacencies)
 58             {
 59                 Vertex v = e.target;
 60                 double weight = e.weight;
 61                 double distanceThroughU = u.minDistance + weight;
 62         if (distanceThroughU < v.minDistance) {
 63             vertexQueue.remove(v);
 64 
 65             v.minDistance = distanceThroughU ;
 66             v.previous = u;
 67             vertexQueue.add(v);
 68         }
 69             }
 70         }
 71     }
RayCW
  • 174
  • 2
  • 10
Ivan-Mark Debono
  • 15,500
  • 29
  • 132
  • 263
  • related: http://stackoverflow.com/questions/15392289/java-using-a-fibonacci-heap-for-implementing-dijkstras-algorithm Is this really a question? – kutschkem Jun 16 '15 at 09:56

1 Answers1

1

Yes, you can.

The suggested implementation has a major performance flaw:

 62         if (distanceThroughU < v.minDistance) {
 63             vertexQueue.remove(v);
 64 
 65             v.minDistance = distanceThroughU ;
 66             v.previous = u;
 67             vertexQueue.add(v);
 68         }

The problem with this piece of code, is removing an arbitrary (not the root) node v from a the priority queue is done in linear time. Java Docs:

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

In a fibonacci heap however, you can change the priority of a node much more efficiently.

amit
  • 175,853
  • 27
  • 231
  • 333
  • This fact is summarised nicely by the wikipedia entry https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times. – Captain Giraffe Jun 16 '15 at 09:57
  • 1
    Is it just a problem of priority queue implementation? Because you _can_ implement priority queue in such a way that changing the priority (as well a deletion of arbitrary element) works in `O(log N)` time. You just need to keep reference where each object is located and update them on every queue update. Though it still seems that in Fibonacci heap you can do priority change in `O(1)`. – Petr Jun 16 '15 at 11:59
  • 1
    @Petr This is a problem in the specific implementation in the piece of code used in the question, that uses java's PriorityQueue, which is inefficient for removal of arbitrary elements, as the java docs says. I am not claiming it cannot be done more efficiently, I am claiming this implementation is not efficient. – amit Jun 16 '15 at 12:07