Java:使用斐波那契堆实现 Dijkstra 算法

Question

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

好的，所以我一直在尝试使用 Fibonacci 堆(在 Java 中)执行 Dijkstra 的最短路径算法。经过一些搜索，我设法偶然发现了两个代表斐波那契堆的现成实现。第一个实现相当漂亮，可以找到 here .第二个实现，看起来不太优雅，是 here .

现在，这一切看起来都很好。但是，我想将其中一种实现用于我的 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 方法的修改版本，它使用前面链接的第二个 Fibonacci 堆实现:

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 实现。我更愿意使用第一个实现来完成它(它看起来更彻底/更专业)但不幸的是我不知道如何去做。

Answer 1

您似乎缺少使用 Double.POSITIVE_INFINITY 添加堆中的所有节点(距离为 0.0 的源节点除外)。这就是您遇到 NullPointerExceptions 的原因，它们根本不在堆中。

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