0

我正在使用 PriorityQueue 为大学研究 Dijkstra 算法来存储我的图形的剩余顶点，按最短遍历距离排序。我使用的比较器：

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))。

我怎样才能消除每次调整比较器的需要？

4

1 回答 1

2

在 Java 中实现 Dijkstra 算法的传统方式是创建一个包含节点和距离的单独类：

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-18T02:18:22.000 回答