PriorityQueue无法正常工作

我试图在java中自己实现Dijkstra算法。我有一个最小优先级队列，存储按当前最短路径排序的节点。PriorityQueue无法正常工作

第一步顺利，I SET起始节点与距离0和其他人Integer.MAX_VALUE的。开始节点被正确地查询出来。但是，在我删除第一个节点后，删除的第二个节点不是距离最小的节点。我无法弄清楚为什么。有什么意见？

这里是我的代码

public void Dijkstra(Node s){ 
    initialize(s); 
    List<Node> set = new ArrayList<Node>(); 
    Comparator<Node> c = new CompareNode(); 
    PriorityQueue<Node> Q = new PriorityQueue<Node>(V,c); 
    for (Node q: Nodes){ 
     Q.add(q); 
    } 
    while (Q.size()!=0){ 
     Node u = Q.remove(); 
     System.out.println(); 
     System.out.println(u + " is removed with dis " + u.getD()); 
     set.add(u); 
     for (Node w: u.getWeightedAdj().keySet()){ 
      relax(u,w); 
     } 
    } 
} 

public void initialize(Node s){ 
    for (Node v: Nodes){ 
     v.setD(Integer.MAX_VALUE); 
     v.setPredecessor(null); 
    } 
    s.setD(0); 
} 

public void relax(Node u, Node w){ 
    if (w.getD()>u.getD()+u.getWeightedAdj().get(w)){ 
     w.setD(u.getD()+u.getWeightedAdj().get(w)); 
     w.setPredecessor(u); 
    } 
}

和比较级

import java.util.Comparator; 

public class CompareNode implements Comparator<Node> { 

@Override 
public int compare(Node o1, Node o2) { 
    if (o1.getD()>o2.getD()) 
     return 1; 
    if (o1.getD()<o2.getD()) 
     return -1; 
    return 0; 
    } 
}

，当我跑了，结果是这样的

A is removed with dis 0 

E is removed with dis 2147483647 

C is removed with dis 2 

D is removed with dis -2147483648 

B is removed with dis 3

来源

2017-05-04 Linrong

请注意，您的代码缺少更改优先级步骤。 java优先级队列中的更改优先级不是自动的。而且它不提供改变优先级的方法。请参阅链接问题以获得更多 – e4c5

的问题是，时Queue号令元素添加时，假设订单不能更改。

在您的例子所有的距离是MAXINT当节点被添加到队列（除了开始节点），因此它们被放置到队列中有效地以随机的顺序。

你再调整的距离，但时Queue不知道这些调整，以便继续在原来的顺序返回元素。

标准方法是在距离改变时将元素插入优先级队列中。（当一个元素从队列中删除，你需要测试你是否已经访问过的元素，因为相同的元素可以在队列中出现多次。）

来源

2017-05-04 12:41:47

谢谢！在找出优先顺序不会改变之前，我一直在研究这个问题好几个小时。 – Linrong

这将是更容易的节点添加到队列中他们被发现。即在开始时只添加根节点，然后在每次迭代中添加新发现的尚未处理的节点。在迭代步骤中，您需要检查新节点是否在队列中，如果新距离较短，可能会更新它们。

来源

2017-05-04 12:49:15 Shaido

PriorityQueue无法正常工作

回答

相关问题