2 qianheshang qianheshang 于 2016.03.29 12:40 提问

java中的优先队列PriorityQueue不再维护最小优先是怎么回事

用最小优先队列实现Dijkstra算法出现PriorityQueue不再维护最小优先,从队列中弹出一个结点后,队列中其余结点顺序未发生改变,
导致第一个元素不是最小值

2个回答

wojiushiwo945you
wojiushiwo945you   Ds   Rxr 2016.03.29 13:32

根据API说明,这个类的队列首元素是最小的啊。你是怎么使用这个类的呢?

 <p>The <em>head</em> of this queue is the <em>least</em> element with respect to the specified ordering. 
wojiushiwo945you
wojiushiwo945you 回复qianheshang: 我看源码了它是根据传入元素实现Comparable接口指定排序操作的。可能跟你的Node的比较实现有关。
一年多之前 回复
qianheshang
qianheshang public static int[] dijkstra(Node[] node, Node n, int[][] e) { //n为起始点 n.d = 0; PriorityQueue<Node> pn = new PriorityQueue<Node>(); for (int i = 0; i < node.length; i++) { if (node[i] == null) { break; } pn.add(node[i]); } int[] s = new int[pn.size()]; while (pn.size() != 0) { Node u = pn.peek(); Node v = u.next; while (v != null) { relax(u, node[v.id], e[u.id][v.id]); s[v.id] = node[v.id].d; v = v.next; } pn.poll(); } return s; }
一年多之前 回复
qianheshang
qianheshang   2016.03.29 13:59

public static int[] dijkstra(Node[] node, Node n, int[][] e) {
//n为起始点
n.d = 0;
PriorityQueue pn = new PriorityQueue();
for (int i = 0; i < node.length; i++) {
if (node[i] == null) {
break;
}
pn.add(node[i]);
}
int[] s = new int[pn.size()];
while (pn.size() != 0) {
Node u = pn.peek();
Node v = u.next;
while (v != null) {
relax(u, node[v.id], e[u.id][v.id]);
s[v.id] = node[v.id].d;
v = v.next;
}
pn.poll();
}
return s;
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!