Java: Using a Fibonacci Heap for Implementing Dijkstra's Algorithm

Question

New here, but have been lurking as a guest for quite some time :)

Okay, so I've been trying to do Dijkstra's shortest path algorithm using a Fibonacci heap (in Java). After some search, I managed to stumble across two ready-made implementations representing a Fibonacci heap. The first implementation is rather beautifully well done and can be found here. The second implementation, seemingly less elegant, is here.

Now, this all looks nice and well. However, I want to use one of those implementations for my version of Dijkstra's algorithm but I have yet to have any luck with that. The implementation of Dijkstra's in use is as follows:

public void dijkstra(Vertex source) {
    {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<>();
        vertexQueue.add(source);

        while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies) {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    vertexQueue.remove(v);
                    v.minDistance = distanceThroughU;
                    v.previous = u;
                    vertexQueue.add(v);
                }
            }
        }
    }
}

As is clear, this implementation uses the Java-based PriorityQueue class (which I believe is based on a binary heap itself). I wish to modify the above code so it uses either of the aforementioned Fibonacci heap implementations instead of Java's PriorityQueue.

I have tried a lot but I just can't figure out how to do it, although I'm sure it's as simple as replacing a few lines of code.

I hope I'm clear enough. This is literally my first post on these boards.

Any help would be greatly appreciated.

EDIT: In response to comments, I figured I would expand my post with one of my attempt scenarios.

Here is a modified version of the above Dijkstra method using the second Fibonacci heap implementation linked earlier:

public static void computePathsFibonacciHeap(Node source) {
    {
        source.minDistance = 0.;
        FibonacciHeap myHeap = new FibonacciHeap();
        myHeap.insert(source, source.minDistance);

        while (!myHeap.isEmpty()) {
            Node u = myHeap.min();

            // Visit each edge exiting u
            for (Edge e : u.adjacencies) {
                Node v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    v.minDistance = distanceThroughU;
                    myHeap.decreaseKey(v, v.minDistance);
                    v.previous = u;
                }
            }
        }
    }
}

This is pretty much converted directly from pseudocode (thus it's entirely possible that I just didn't translate it right). The error I get says "decreaseKey() got a larger value". If I try to remove the minimum, I get a NullPointerException.

I'm sure I'm doing something wrong, and I'd love to know what it is. Once again, this is using the second FHeap implementation. I would have preferred to do it using the first implementation (it just looks a lot more thorough/professional) but I unfortunately couldn't figure out how to.

Answer 1

It seems you are missing to add all the nodes the your heap with Double.POSITIVE_INFINITY (except the source node with 0.0 distance). That's why you are having NullPointerExceptions, they are simply not in the heap.

I made some test on several open-source Fibonacci Heap implementation. You can find the test itself here: Experimenting-with-dijkstras-algorithm. Also this is my Priority Queue version of the Dijsktra's algorithm: PriorityQueueDijkstra.java