新来的，但已经作为客人潜伏了一段时间了:)
好的，所以我一直在尝试使用 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 类（我相信它基于二进制堆本身）。我希望修改上面的代码，以便它使用前面提到的 Fibonacci 堆实现而不是 Java 的 PriorityQueue。
我已经尝试了很多，但我就是不知道该怎么做，尽管我确信它就像替换几行代码一样简单。
我希望我说得足够清楚。这实际上是我在这些板上发表的第一篇文章。
任何帮助将不胜感激。
EDIT:为了回应评论，我想我应该用我的尝试场景之一来扩展我的帖子。
以下是上述 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 实现。我更愿意使用第一个实现来完成它（它看起来更彻底/专业），但不幸的是我不知道如何做。
