java - PriorityQueue 经常需要调整比较器 - 我该如何最好地处理这个问题？

Question

我正在为大学研究 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))变得紧张。

如何消除每次调整比较器的需要？

Answer 1

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

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

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

并将那些放入您的优先级队列中。

您最终会得到反射(reflect)次优路径的过时 Dist 对象，但只有在您已经看到“最佳”路径之后，所以只需忽略您已经见过的顶点从优先级队列中取出。

基本上，不要更改Comparator:更改正在比较的对象。