Dijkstra算法使用優先級隊列

所以我試圖用Java中的優先級隊列中的數據結構來實現Dijkstra算法。？由於Java的可比運營商不能比較兩個變量，所以我需要「修改其Comparator如何修改它Dijkstra算法使用優先級隊列

while(!Q.isEmpty()){ 
     int index = Q.peek().edge; 
     long d = Q.peek().dis; 
     Q.remove(); 

     if(d!=D[index]) continue; // HERE I AM CHECKING IF IT ALREADY PROCEEDED OR NOT 

     for(int i=0;i<maps[index].size();i++){ 
       int e = maps[index].get(i).edge; 
       d = maps[index].get(i).dis; 
       if(D[e]>D[index]+d){ 
        D[e]= D[index]+d; 
        Q.add(new Node(e,D[e])); // NEED TO MODIFY 
       } 
     } 
    }

然後，我遇到了這個代碼：

while (!q.isEmpty()) { 
     long cur = q.remove(); 
     int curu = (int) cur; 
     if (cur >>> 32 != prio[curu]) 
     continue; 
     for (Edge e : edges[curu]) { 
     int v = e.t; 
     int nprio = prio[curu] + e.cost; 
     if (prio[v] > nprio) { 
      prio[v] = nprio; 
      pred[v] = curu; 
      q.add(((long) nprio << 32) + v); 
     }

如何q.add(((long) nprio << 32) + v);和cur >>> 32 != prio[curu]陳述的工作原理請參考

來源

2015-06-19 user4996457

簽署的向左移位運算符「<<」變換位模式向左，和簽名向右移位運算符「>>」移位的位模式的權利。位模式由左側操作數給出，並由右側操作數移動位置數量。無符號右移運算符「>>>」將零移動到最左邊的位置，而「>>」之後的最左邊位置取決於符號擴展。 –

它是如何在上述算法，該算法在優先級比較有用的隊列可以得到它 – user4996457

Java的Priorityqueue根據自然順序進行排序，如果沒有給出比較器的話

您可能需要：

實現的compareTo在Node類
創建根據優先級（優先級=從開始的Dijkstra算法距離）

第二的節點，其比較比較您顯示的代碼使用長整型的高32位來存儲優先級，從而使自然順序反映起點的距離。

基本上，代碼爲100％和你的一樣，區別是數據結構。你使用一個類，第二個代碼使用一個long來嵌入兩個整數（節點ID和距離/優先級）。

來源

2015-06-19 11:25:01 kutschkem

你能解釋一個長期的第二個代碼黑客利用i.e32位優先 – user4996457

存儲@ user4996457由於它們的較高位，他們正在確定訂單。 – kutschkem

Dijkstra算法使用優先級隊列

回答

相關問題