使用現有的斐波那契堆Java實現與Dijkstra的最短路徑Java實現

Question

使用java編程語言，我試圖在具有正邊緣成本的圖上實現最有效的最短路徑算法。據我所知，這將是Dijkstra的算法與斐波那契堆作爲優先級隊列。正如鏈接中所述，我借用了Keith Schwarz以下的斐波那契堆實現。 http://keithschwarz.com/interesting/code/?dir=fibonacci-heap

在我的代碼，我還修改了在這個問題上提出的Dijkstra算法實現，

Java: Using a Fibonacci Heap for Implementing Dijkstra's Algorithm

，這裏是我更新的Dijkstra根據我的實現，

public static void SPFibonacciHeap() { 
    { 

     FibonacciHeap<Node> myHeap = new FibonacciHeap<Node>(); 

     //adding all nodes to the PQ (heap) 
     for(int i=0; i<nodeList.size(); i++) 
        myHeap.enqueue(nodeList.get(i), nodeList.get(i).d); 

     while (!myHeap.isEmpty()) { 

      //deque the minimum (first iteration will be the source) 
      Entry<Node> u = myHeap.dequeueMin(); 


      // Visit each edge connected from u 
      for (AdjacentNode a : u.getValue().adjacents) { 

       //getting the adjacent node 
       Node v = a.node; 
       Entry<Node> vEntry = new Entry<Node>(v,v.d);//WRONG 

       //getting the edge weight 
       double weight = a.cost; 

       double distanceThroughU = u.getValue().d + weight; 
       if (distanceThroughU < v.d) { 
        v.d = distanceThroughU; 
        myHeap.decreaseKey(vEntry, v.d); //SHOWS ERROR 
        v.parent = u.getValue(); 
       } 
      } 
     } 
    } 
} 

這裏是我的節點，和相鄰節點類別，

class Node{ 

    Double [] label; 
    double d; //node cost 
    ArrayList<AdjacentNode> adjacents; 
    Node parent; 

    public Node(Double[] label, double d,ArrayList<AdjacentNode> adjacents) 
    { 
     this.label= label; 
     this.d=d; 
     this.adjacents=adjacents; 
     parent=null; 

    } 




} 


class AdjacentNode 
{ 
    Node node; 
    double cost; 

    public AdjacentNode(Node node, double cost) 
    { 
     this.node= node; 
     this.cost=cost; 
    } 
} 

一切都很好，直到我想減小鍵在下面的行，

myHeap.decreaseKey(vEntry, v.d); 

我現在面臨的問題是，vEntry應堆中已經存在的節點。但是，我無法從堆中檢索此節點，因爲我可以考慮檢索相鄰節點v的唯一方法是使用節點u中的鄰接列表。但後來，我錯誤地代表它在下面的行一個新的入口節點，

Entry<Node> vEntry = new Entry<Node>(v,v.d); 

然而，這將創建一個新的條目抱着我找的，而不是在堆中存在與節點的條目中的節點我在尋找。如預期的那樣，這導致空指針異常。

我無法弄清楚這個問題的解決方案。是否獲得與給定節點條目相鄰的節點條目對於此堆實現似乎不可行？有人可以幫忙嗎？謝謝。

Answer 1

所以...這是我的代碼。 :-)我想我可能可以在這裏幫忙。

如果你會注意到，enqueue方法返回一個Entry<T>表示Fibonacci堆中的內部條目對應於剛剛入隊的對象。其意圖是，當你將某些東西放入斐波那契堆中時，你會保存Entry<T>你回到某個地方，以便稍後可以使用它。我其實在我的網站上也有an implementation of Dijkstra's algorithm。我做這項工作的方法是將第二個Map從節點存儲到Entry對象，以便當我需要呼叫decreaseKey時，我可以查找對應於給定節點的Entry，然後將其傳遞到decreaseKey。

作爲擡頭，而Dijkstra的一個斐波那契堆算法是理論上比使用像一個普通的二叉堆更快，在實踐它往往是慢了很多，因爲在斐波那契數的常數因子堆是如此之高。這是由於許多因素（指針玩雜耍，大量的連接結構和糟糕的位置等），所以如果你的目標是獲得最快的牆上時鐘速度，你可能只想使用普通的老式二進制堆。即使你想使用斐波那契堆，你也可以嘗試優化我發佈的實現 - 我寫的目標是正確和清晰，而不是原始效率。