PriorityQueue無法正常工作

我試圖在java中自己實現Dijkstra算法。我有一個最小優先級隊列，存儲按當前最短路徑排序的節點。PriorityQueue無法正常工作

第一步順利，I SET起始節點與距離0和其他人Integer.MAX_VALUE的。開始節點被正確地查詢出來。但是，在我刪除第一個節點後，刪除的第二個節點不是距離最小的節點。我無法弄清楚爲什麼。有什麼意見？

這裏是我的代碼

public void Dijkstra(Node s){ 
    initialize(s); 
    List<Node> set = new ArrayList<Node>(); 
    Comparator<Node> c = new CompareNode(); 
    PriorityQueue<Node> Q = new PriorityQueue<Node>(V,c); 
    for (Node q: Nodes){ 
     Q.add(q); 
    } 
    while (Q.size()!=0){ 
     Node u = Q.remove(); 
     System.out.println(); 
     System.out.println(u + " is removed with dis " + u.getD()); 
     set.add(u); 
     for (Node w: u.getWeightedAdj().keySet()){ 
      relax(u,w); 
     } 
    } 
} 

public void initialize(Node s){ 
    for (Node v: Nodes){ 
     v.setD(Integer.MAX_VALUE); 
     v.setPredecessor(null); 
    } 
    s.setD(0); 
} 

public void relax(Node u, Node w){ 
    if (w.getD()>u.getD()+u.getWeightedAdj().get(w)){ 
     w.setD(u.getD()+u.getWeightedAdj().get(w)); 
     w.setPredecessor(u); 
    } 
}

和比較級

import java.util.Comparator; 

public class CompareNode implements Comparator<Node> { 

@Override 
public int compare(Node o1, Node o2) { 
    if (o1.getD()>o2.getD()) 
     return 1; 
    if (o1.getD()<o2.getD()) 
     return -1; 
    return 0; 
    } 
}

，當我跑了，結果是這樣的

A is removed with dis 0 

E is removed with dis 2147483647 

C is removed with dis 2 

D is removed with dis -2147483648 

B is removed with dis 3

來源

2017-05-04 Linrong

請注意，您的代碼缺少更改優先級步驟。 java優先級隊列中的更改優先級不是自動的。而且它不提供改變優先級的方法。請參閱鏈接問題以獲得更多 – e4c5

的問題是，時Queue號令元素添加時，假設訂單不能更改。

在您的例子所有的距離是MAXINT當節點被添加到隊列（除了開始節點），因此它們被放置到隊列中有效地以隨機的順序。

你再調整的距離，但時Queue不知道這些調整，以便繼續在原來的順序返回元素。

標準方法是在距離改變時將元素插入優先級隊列中。（當一個元素從隊列中刪除，你需要測試你是否已經訪問過的元素，因爲相同的元素可以在隊列中出現多次。）

來源

2017-05-04 12:41:47

謝謝！在找出優先順序不會改變之前，我一直在研究這個問題好幾個小時。 – Linrong

這將是更容易的節點添加到隊列中他們被發現。即在開始時只添加根節點，然後在每次迭代中添加新發現的尚未處理的節點。在迭代步驟中，您需要檢查新節點是否在隊列中，如果新距離較短，可能會更新它們。

來源

2017-05-04 12:49:15 Shaido

PriorityQueue無法正常工作

回答

相關問題