2
新，但都被潛伏作爲嘉賓在相當一段時間:)的Java：使用斐波那契堆在這裏實現Dijkstra算法
好了，所以我一直在嘗試使用斐波納契做Dijkstra的最短路徑算法堆（Java）。經過一番搜索之後，我設法絆倒了代表Fibonacci堆的兩個現成實現。第一個實現相當出色，可以找到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。
我已經嘗試了很多，但我只是無法弄清楚如何去做，儘管我確信它就像替換幾行代碼一樣簡單。
我希望我很清楚。這實際上是我在這些電路板上的第一篇文章。
任何幫助將不勝感激。
編輯：在迴應的意見，我想我會擴大我的職務與我的企圖方案之一。
這裏是上述最短路徑法使用鏈接的第二斐波那契堆實現更早的修改版：
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實現。我寧願使用第一個實現（它看起來更徹底/專業），但我不知道如何去做。
向我們展示您嘗試過的以及您失敗的位置。我們將爲此提供幫助。 – 2013-03-13 17:29:11
完成。謝謝你提醒我。 – 2013-03-13 17:46:36