Java: Using a Fibonacci Heap for Implementing Dijk

问题:

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.

回答1:

The JDK does not provide an implementation of the Fibonacci Heap. You will have to create your own implementation, or you can find one in this post: Fibonacci Heap

All you have to afterwards is replacing

PriorityQueue<Vertex> vertexQueue = new PriorityQueue<>();

by

 FibonacciHeap<Vertex> vertexQueue = new FibonacciHeap<>();

Then simply change the calls to thepoll, add and remove methods with their equivalent in your provided implementation.

回答2:

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

回答3:

I worked with this algorithm myself. There is a comment above the decreaseKey function which explains the behaviour.

Decreases the key of the specified element to the new priority. If the new priority is greater than the old priority, this function throws an IllegalArgumentException. The new priority must be a finite double, so you cannot set the priority to be NaN, or +/- infinity. Doing so also throws an IllegalArgumentException. It is assumed that the entry belongs in this heap. For efficiency reasons, this is not checked at runtime.

As for the implementation, I think you would want to use myHeap.dequeueMin().getValue() instead of myHeap.min(). The difference is, dequeueMin() works like poll() and removes it from the heap after finding it.

And instead of myHeap.decreaseKey(v, v.minDistance), simply add it, like myHeap.insert(v, v.minDistance).