2

新来的，但作为客人潜伏了很长一段时间:)

好的，所以我一直在尝试使用斐波那契堆（在 Java 中）做 Dijkstra 的最短路径算法。经过一番搜索，我偶然发现了两个代表斐波那契堆的现成实现。第一个实现做得相当漂亮，可以在这里找到。第二个实现，看起来不那么优雅，在这里。

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

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。

我已经尝试了很多，但我就是不知道该怎么做，尽管我确信它就像替换几行代码一样简单。

我希望我足够清楚。这实际上是我在这些板上的第一篇文章。

任何帮助将不胜感激。

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

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

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

这几乎是直接从伪代码转换而来的（因此完全有可能我只是没有正确翻译它）。我得到的错误是“decreaseKey() 的值更大”。如果我尝试删除最小值，我会得到 NullPointerException。

我确定我做错了什么，我很想知道它是什么。再次，这是使用第二个 FHeap 实现。我宁愿使用第一个实现来做到这一点（它看起来更彻底/更专业），但不幸的是我不知道如何去做。

4

3 回答 3

1

似乎您缺少使用 Double.POSITIVE_INFINITY 将所有节点添加到堆中（距离为 0.0 的源节点除外）。这就是为什么你有 NullPointerExceptions，它们根本不在堆中。

我对几个开源斐波那契堆实现做了一些测试。您可以在此处找到测试本身：Experimenting-with-dijkstras-algorithm。这也是我的 Dijsktra 算法的优先队列版本：PriorityQueueDijkstra.java

于 2015-02-15T18:25:16.387 回答
0

JDK 不提供斐波那契堆的实现。您必须创建自己的实现，或者您可以在这篇文章中找到一个：Fibonacci Heap

之后你所要做的就是更换

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

经过

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

然后只需在您提供的实现中使用等效的方法更改对poll,add和方法的调用。remove

于 2013-03-13T17:35:28.487 回答
0

我自己使用过这个算法。reduceKey函数上方有一条注释，解释了该行为。

将指定元素的键降低到新的优先级。如果新优先级大于旧优先级，则此函数将引发 IllegalArgumentException。新的优先级必须是有限双精度，因此您不能将优先级设置为 NaN 或 +/- 无穷大。这样做也会引发 IllegalArgumentException。假设条目属于这个堆。出于效率原因，在运行时不检查此项。

至于实现，我想你会想使用myHeap.dequeueMin().getValue()而不是myHeap.min()。不同之处在于，dequeueMin()的工作方式与poll()类似，并在找到它后将其从堆中删除。

而不是myHeap.decreaseKey(v, v.minDistance)，只需添加它，例如myHeap.insert(v, v.minDistance)。

于 2015-10-07T10:58:40.180 回答