logo标签列表

Dijkstra算法求解最短路径

javaalgorithmdijkstra
8
我目前正在重新完成一项旧的家庭作业，其中我编写了一个程序，其中包括使用Dijkstra算法在图中查找最短路径等功能。我认为大部分都正确，但是执行if(currentNode.getAktuell())时，在第58行不断出现NullPointerException。
我已经尝试了多种解决方案，但似乎无法弄清楚问题所在，因为当队列为空时，prioQueue.poll()返回null。我尝试处理最后一个currentNode，但没有找到有效的解决方案，因此我开始认为我在这里错过了什么。
如果熟悉Dijkstra算法的人能帮助我，我将不胜感激。该算法可能有更好的解决方案，但我只想寻求关于我编写的算法存在的问题，而不是使用其他人的算法“答案”。
public static List<String> shortestPath(Graph<String> graph, String från, String till){

    //if(!pathExists(graph, från, till))
    //return null;

    PriorityQueue<DjikstraObjekt<String>> prioQueue = new PriorityQueue<DjikstraObjekt<String>>();
    LinkedHashMap<String, DjikstraObjekt<String>> samling = new LinkedHashMap<String, DjikstraObjekt<String>>();

    for(String bla : graph.getNodes())
        samling.put(bla, new DjikstraObjekt<String>(bla, Integer.MAX_VALUE, null, false));
    samling.get(från).updateVikt(0);
    prioQueue.add(samling.get(från));

    while(!samling.get(till).getAktuell())
    {

        DjikstraObjekt<String> currentNode = prioQueue.poll();
        if(currentNode==null)
            break;
        if(currentNode.getAktuell())
            continue;


        currentNode.aktuellNod();

        for(ListEdge<String> edge : graph.getEdgesFrom(currentNode.getNode()))
        {
            System.out.println("get edges from");
            int nyVikt = edge.getVikt() + currentNode.getVikt();
            DjikstraObjekt<String> toNode = samling.get(edge.getDest());
            if(!toNode.getAktuell() && nyVikt < toNode.getVikt()) {
                toNode.updateVikt(nyVikt);
                toNode.setFrån(currentNode.getNode());
                prioQueue.add(toNode);
            }
        }

    }       

    List<String> djikstaList = new ArrayList<String>();
    for(int i=0;i<samling.size();i++){
        if(samling.get(i).getNode()!=från){
            System.out.println(samling.get(i).getNode());
            djikstaList.add(samling.get(i).getNode());
        }       
    }

    return djikstaList;
}


public class DjikstraObjekt<E> implements Comparable<DjikstraObjekt<E>> {
    private E nod;
    private int vikt;
    private E frånNod;
    private boolean aktuellNod=false;

    public DjikstraObjekt(E nod, int vikt, E frånNod, boolean aktuellNod){

        this.nod=nod;
        this.vikt=vikt;
        this.frånNod=frånNod;
        this.aktuellNod=aktuellNod;

    }
    public E getNode() {
        return nod;
    }
    public void updateVikt(int nyvikt){
        vikt=nyvikt;
    }
    public int getVikt() {
        return vikt;
    }
    public boolean getAktuell() {
        return aktuellNod;
    }
    public void aktuellNod(){
        aktuellNod=true;
    }
    public void setFrån(E från)
    {
        frånNod = från;
    }
    public int compareTo(DjikstraObjekt<E> other) {
        return getVikt() - other.getVikt();
    }
}

这是我的列表边缘类：
public class ListEdge<E> {

    private E dest;
    private String namn;
    private Integer vikt;


    public ListEdge(E dest, String namn, Integer vikt){
        this.dest=dest;
        this.namn=namn;
        this.vikt=vikt;

    }

    public E getDest(){
        return dest;
    }
    public void ändraVikt(Integer nyVikt){
        if(vikt<0)
            throw new IllegalArgumentException();
        vikt=nyVikt;

        }
    public String getNamn(){
        return namn;
    }
     public int compareTo(ListEdge other) {
         return this.vikt.compareTo(other.getVikt());
 }

    public int getVikt(){
        return vikt;
    }
    public String toString(){
        return "till " + dest + " med " + namn +" "+ vikt;
    }
}

以下是我的ListGraph类中相关的方法：

public List<E> getNodes(){
    List<E> temp = new ArrayList<E>();
    for(E test : noder.keySet()){
        temp.add(test);

    }
return temp;
}

public List<ListEdge<E>> getEdgesFrom(E nod) {
        List<ListEdge<E>> temp = new ArrayList<ListEdge<E>>();
        if(noder.containsKey(nod)){
            try{
                for(Map.Entry<E, List<ListEdge<E>>> test : noder.entrySet()){
                    if(test.getKey().equals(nod)){
                        System.out.println(nod+" "+test.getKey());
                        for(ListEdge<E> e: test.getValue()){
                            temp.add(e);
                    }
                }
            }
        }
            catch(NoSuchElementException E){

            }

        }
        return temp;
    }
9
对于非斯堪的纳维亚人而言，“vikt”表示“重量”，“från”表示“来自”，“aktuell”表示“当前的”。 - Aasmund Eldhuset
是的，对不起。我有一个坏习惯，经常混淆英语和瑞典语的变量/方法名称 :) - John Snow
请提供您的DijkstraObject代码或完整的堆栈跟踪。由于在该行之前检查了“currentNode”是否为“null”，因此“NullPointerException”必须源自“getAktuell（）”方法。 - Frank
我在页面底部包含了DijkstraObject类。 - John Snow
1
如果您提供Graph和ListEdge类，将更容易找到错误。如果您还没有解决它，请提交相关信息。我对此很好奇 :) - Leandro
嗨！我已经在我的主贴中添加了相关方法，这些方法将是我的ListEdge类和图形中的相关方法。请让我知道如果你能找出问题是什么 :) - John Snow
3个回答
3

我无法重现你所描述的空指针异常情况。正如Leandro所指出的那样，问题可能在于您对ListEdge和Graph的实现。

为了测试您的代码，我自己实现了这两个类。

我发现的唯一问题是在最后创建结果列表的地方：

for(int i=0;i<samling.size();i++){
        if(samling.get(i).getNode()!=från){

这将始终导致NullPointerException，因为get()方法期望的是一个键，而在您的情况下，它是一个String，而不是一个int。要遍历Map，请使用类似以下的代码：

List<String> djikstaList = new ArrayList<String>();
for(String key : samling.keySet()){
    if(samling.get(key).getNode()!=från){
        System.out.println(samling.get(key).getNode());
        djikstaList.add(samling.get(key).getNode());
    }       
}

此外，我假设您希望返回从from到to的实际路径，因此您需要向DijkstraObjekt添加一个gettergetFrån()，然后像这样构建列表：
   String fromNode = samling.get(to).getNode();
   djikstaList.add(to);
   while(fromNode != from){   
       fromNode = samling.get(fromNode).getFrån();
       djikstaList.add(fromNode);
   }

接下来，列表将包含完整路径（包括起点和终点），但顺序是相反的。

如果需要，我可以发布我用于测试/调试的所有类。

祝好 tannerli

嗨！我已经编辑了我的主帖，添加了图中缺失的方法。目前不在家，所以还无法尝试你的答案，但如果能够通过你的答案解决问题，我会告诉你的。 - John Snow
我发现你添加的这两个类没有明显的问题（虽然拥有整个ListGraph类会更好），我认为问题仍然停留在我提到的那部分，因为我不需要改变算法本身的逻辑就能让它正常工作。 - tannerli
感谢您的帮助。我现在正在度假，但我会尝试您的建议，并在两周后回家后将其标记为已解决，如果我能让它工作的话 :) - John Snow
我让算法正常工作了。像你说的那样，我之前以错误的方式构建了列表。我还在djikstraObject类中添加了从哪个节点来以及以何种方式的信息。非常感谢你，你是我的救命恩人 :) - John Snow
很高兴能帮忙，反正我也得为我的“数据结构和算法”考试学习 :) - tannerli
0

我认为这可能是一个问题：

//...
samling.put(bla, new DjikstraObjekt<String>(bla, Integer.MAX_VALUE, null, false));
samling.get(från).updateVikt(0);

编辑：

抱歉，我以为 {} 已经在那里了。那里一切正常。我会继续寻找。

0

也许可以尝试这个：

if(currentNode==null || currentNode.getAktuell() == null)
         break;        
if(currentNode.getAktuell())            
        continue;
我之前尝试过，但后面的代码会给我一个空指针。我觉得我在这里做错了其他事情，但是想不出来是什么。 - John Snow
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接