Improving on Dijkstra using Fibonacci heaps?

Question

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     }

Answer 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.