PriorityQueue經常需要調整比較器 - 我如何處理這個最好？

我正在使用PriorityQueue來存儲大學的Dijkstra算法，以存儲我的圖的其餘頂點，按最短遍歷距離排序。的比較我用：PriorityQueue經常需要調整比較器 - 我如何處理這個最好？

class DistanceComparator implements Comparator<Integer> { 
    int[] dist; 
    public DistanceComparator(int[] d) { 
     dist = d; 
    } 

    @Override 
    public int compare(Integer i, Integer j) 
    { 
     if((dist[i]-dist[j]) < 0) { 
      return -1; 
     } 
     if((dist[i]-dist[j]) > 0) { 
      return 1; 
     } 
     return 0; 
    } 
}

現在我面臨的問題是，距離發生變化，所以我的隊列的比較將需要經常更新。

static PriorityQueue<Integer> refreshQueue(int[] d) { 
    Comparator<Integer> comp = new DistanceComparator(d); 
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(adj.length, comp); 
    for(int i = 0; i < adj.length; i++) { 
     q.add(i); 
    } 
    return q; 
}

這是卓有成效的，但它也將應變所需的運行O(num Edges*log(num Vertices))。

如何避免每次都需要調整比較器？

來源

2012-06-18 Ben

實現Dijkstra的Java中的算法，傳統的方法是創建一個包含節點和距離的單獨的類：

class Dist implements Comparable<Dist> { 
    final int vertex; 
    final int distance; 

    public int compareTo(Dist other) { 
    return Integer.compare(distance, other.distance); 
    } 
}

，並把這些到你的優先級隊列。

您將以反映次優路徑的過期Dist對象結束，但只有在您已經看到「最佳」路徑後，才忽略已從優先隊列中取出的頂點。

基本上，不要更改Comparator：更改被比較的對象。

來源

2012-06-18 02:18:22

PriorityQueue經常需要調整比較器 - 我如何處理這個最好？

回答

相關問題