java - 如何为 Dijkstra 算法实现 PriorityQueue？

Question

我有一个关于为 Dijkstra 算法实现优先级队列的问题，因为这是一个硬件，所以我无法创建另一个类，所以我试图找到一种方法来在优先级队列中添加节点(整数)，但我想要队列对节点内的权重进行排序，而不是节点本身。

例如，我有 3 个节点 (0,1,2)，节点 0 的权重为 10，节点 1 的权重为 15，节点 2 的权重为 5。

Queue<Integer> queue = new PriorityQueue<Integer>();
queue.add(0);
queue.add(1);
queue.add(2);

while(!queue.isEmpty()){
    System.out.println(queue.poll());
}

这应该给我输出 2,0,1。 如果不创建另一个类，这可能吗？或者除了优先级队列之外，我还可以使用其他方法吗？

提前致谢!!!!!!任何帮助将不胜感激!

我能想到的一个解决方案是每次向其中添加一个节点时对普通队列进行排序，所以如果我在队列中有节点 2,0,1 并且我想添加权重为 8 的节点 3，我需要将权重与队列的顶部元素进行比较，直到它适合队列，因此它在队列中为 2,3,0,1，但这有点低效。

Answer 1

你有两个选择:

1. 创建您自己的 Node类，并让它实现 Comparable<Node>界面。该类将有一个 weight属性，它可以比较 Node这是基于他们的体重。这将创建一个 natural ordering的 Nodes那PriorityQueue会用。

2. 用 PriorityQueue(Comparator<? super E> comparator) 创建优先级队列构造函数。它需要一个比较函数 ( Comparator ) 来比较两个项目。因此，您可以使用节点的权重来比较该函数(不必保存在同一队列中 - 可以动态计算或保存在一些单独的数据结构中)。