gpt4 book ai didi

java - Dijkstra算法-优先级队列问题

转载 作者:行者123 更新时间:2023-11-30 04:35:38 32 4
gpt4 key购买 nike

我有一个带有一堆节点、边等的 Graph 类,我正在尝试执行 Dijkstra 算法。我首先将所有节点添加到优先级队列中。每个节点都有一个 boolean 标志(表示它是否已经“已知”)、对其之前节点的引用,以及一个存储其距源节点的长度的 int dist 字段。将所有节点添加到 PQ 并适当标记源节点后,我注意到错误的节点首先从 PQ 中拉出。应该是具有最小 dist 字段的节点首先出现(因为除了源之外,它们都被初始化为一个非常高的数字,所以 PQ 中的第一个节点应该是源......除非它不是某些原因)。下面是我的算法代码,后面是 Node 类中的比较方法。

    public void dijkstra() throws IOException {
buildGraph_u();
PriorityQueue<Node> pq = new PriorityQueue<>(200, new Node());

for (int y = 0; y < input.size(); y++) {
Node v = input.get(array.get(y));
v.dist = 99999;
v.known = false;
v.prnode = null;
pq.add(v);
}

source.dist = 0;
source.known = true;
source.prnode = null;
int c=1;
while(c != input.size()) {
Node v = pq.remove();
//System.out.println(v.name);
//^ Prints a node that isn't the source
v.known = true;
c++;
List<Edge> listOfEdges = getAdjacent(v);
for (int x = 0; x < listOfEdges.size(); x++) {
Edge edge = listOfEdges.get(x);
Node w = edge.to;
if (!w.known) {
int cvw = edge.weight;
if (v.dist + cvw < w.dist) {
w.dist = v.dist + cvw;
w.prnode = v;
}
}
}
}
}
<小时/>
public int compare (Node d1, Node d2) {
int dist1 = d1.dist;
int dist2 = d2.dist;
if (dist1 > dist2)
return 1;
else if (dist1 < dist2)
return -1;
else
return 0;
}

谁能帮我找出 PQ 的问题吗?

最佳答案

优先级队列假设插入元素后顺序不会改变。

因此,您可以:

,而不是将所有元素插入到优先级队列中
  1. 从一个节点开始。

  2. 当优先级队列不为空时循环。

  3. 如果元素“已知”,则不执行任何操作。

  4. 每当您发现较小的距离时,请将其添加到具有“正确”权重的优先级队列中。

  5. 因此,您需要在优先级队列中存储其他内容,一对:插入时的距离、节点本身。

关于java - Dijkstra算法-优先级队列问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13594699/

32 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com