Ivan-Mark Debono - 1 year ago 127
Java Question

# Improving on Dijkstra using Fibonacci heaps?

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>();
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;
68         }
69             }
70         }
71     }
``````

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;
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: