Java：使用斐波那契堆实现Dijkstra算法 [英] Java: Using a Fibonacci Heap for Implementing Dijkstra's Algorithm

问题描述

这里新增，但已经潜入客人一段时间了：）

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

好的，所以我一直在尝试用Dijkstra的最短路径算法斐波那契堆（在Java中）。经过一番搜索，我设法绊倒了代表斐波纳契堆的两个现成的实现。第一个实现是相当完美的，可以在 here 找到。第二个实施方式似乎不太优雅，是此处。

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.

现在，这一切都看起来不错，很好。但是，我想使用我的Dijkstra的算法的其中一个实现，但我还没有运气。使用Dijkstra的实现如下：

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);
                }
            }
        }
    }
}

很明显，此实现使用基于Java的PriorityQueue类（我认为基于二进制堆本身）。 我希望修改上面的代码，所以它使用上述的斐波那契堆实现，而不是Java的PriorityQueue。

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.

任何帮助将不胜感激。

编辑： / strong>为了回应评论，我想我会用我的一个尝试场景扩展我的帖子。

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

以下是使用之前链接的第二个斐波那契堆实现的上述Dijkstra方法的修改版本：

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

这几乎直接从伪代码转换（因此完全可能我没有正确地翻译它）。我得到的错误说reduceKey（）获得了更大的值。如果我尝试删除最小值，我得到一个NullPointerException。

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.

我确定我做错了，我很想知道它是什么。再次，这是使用第二个FHeap实现。我会喜欢使用第一个实现（它只是看起来更彻底/专业），但我不幸的是无法弄清楚如何。

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.

推荐答案

我自己处理了这个算法。

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

将指定的元素的键减小到新的优先。如果新的优先级大于旧的优先级，则此函数会抛出
IllegalArgumentException。新的优先级必须是有限的double
，所以您不能将优先级设置为NaN或+/-无穷大。做
所以也会抛出一个IllegalArgumentException。
假定该条目属于此堆。对于效率
的原因，这在运行时没有检查。

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.

至于实现，我想你会想使用 myHeap.dequeueMin（）。getValue（），而不是 myHeap.min（）。不同之处在于，dequeueMin（）的工作原理像poll（），并在找到它之后将其从堆中删除。

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.

而不是 myHeap.decreaseKey（v，v.minDistance），只需添加它，如 myHeap.insert（v， v.minDistance）。

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

这篇关于Java：使用斐波那契堆实现Dijkstra算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！