Java：使用Fibonacci堆实现Dijkstra算法
在这里新，但作为客人已经潜伏了相当长的一段时间:)
好吧，所以我一直在尝试使用Fibonacci堆（在Java中）做Dijkstra的最短路径算法。 经过一些搜索，我设法偶然发现了两个代表Fibonacci堆的现成实现。 第一个实现相当精美，可以在这里找到。 第二个实现，似乎不那么优雅，就在这里 。
现在，这一切看起来都很好。 但是，我想在我的Dijkstra算法版本中使用其中一个实现，但我还没有运气。 Dijkstra的使用实施如下：
public void dijkstra(Vertex source) { { source.minDistance = 0.; PriorityQueue 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类（我相信它基于二进制堆本身）。 我希望修改上面的代码，以便它使用前面提到的Fibonacci堆实现中的任何一个而不是Java的PriorityQueue。
我已经尝试了很多，但我无法弄清楚如何做到这一点，虽然我确信它就像更换几行代码一样简单。
我希望我足够清楚。 这是我在这些主板上的第一篇文章。
任何帮助将不胜感激。
编辑：在回应评论时，我想我会用我的一个尝试场景扩展我的post。
以下是使用之前链接的第二个Fibonacci堆实现的上述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实现。 我宁愿使用第一个实现（它只是看起来更彻底/专业），但遗憾的是我无法弄清楚如何。
JDK不提供Fibonacci Heap的实现。 您将不得不创建自己的实现，或者您可以在这篇文章中找到一个： Fibonacci Heap
之后你所要做的就是更换
PriorityQueue vertexQueue = new PriorityQueue<>();
通过
FibonacciHeap vertexQueue = new FibonacciHeap<>();
然后只需更改对poll的调用，在提供的实现中add和remove等效方法。
您似乎缺少使用Double.POSITIVE_INFINITY添加堆的所有节点（除了距离为0.0的源节点）。 这就是你有NullPointerExceptions的原因，它们根本就不在堆中。
我对几个开源的Fibonacci Heap实现进行了一些测试。 您可以在这里找到测试本身： Experimenting-with-dijkstras-algorithm 。 这也是我的Dijsktra算法的Priority Queue版本： PriorityQueueDijkstra.java
我自己使用这个算法。 reduceKey函数上面有一个注释，用于解释行为。
将指定元素的键减少到新优先级。 如果新优先级大于旧优先级，则此函数将抛出IllegalArgumentException。 新优先级必须是有限倍，因此您不能将优先级设置为NaN或+/-无穷大。 这样做也会抛出IllegalArgumentException。 假设该条目属于此堆。 出于效率原因，不会在运行时检查。
至于实现，我想你会想要使用myHeap.dequeueMin（）。getValue（）而不是myHeap.min（） 。 区别在于， dequeueMin（）的工作方式与poll（）类似，并在找到后将其从堆中删除。
而不是myHeap.decreaseKey（v，v.minDistance） ，只需添加它，如myHeap.insert（v，v.minDistance） 。