使用Dijkstra算法的最短路径

Question

我现在正在恢复旧的家庭作业任务，在那里我正在编写一个程序，其中包括使用Dijkstra算法在图中找到最短路径。

我想我已经明白了，但在执行if(currentNode.getAktuell())时，我一直收到NullPointerException的第58行。

我一直在尝试几种解决方案，但似乎无法弄清楚什么是错误的，但当队列为空时prioQueue.poll();返回null。我试图处理最后currentNode，最终变成空，但一直没有找到一个工作解决方案，所以我开始认为我错过了这里的东西。

如果有人熟悉dijkstras算法可以帮助我，我会非常感激。算法可能有更好的解决方案，但我只想帮助我找出我写的内容有什么问题，而不是使用别人算法的“答案”。

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(); 
    } 
} 

继承人我listEdge类：

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; 
    } 

Answer 1

我不能重建您向我们介绍了NullPointerException异常。正如Leandro指出的那样，这个问题可能与您实现ListEdge和Graph有关。

我自己做了两个类的实现来测试你的代码。

我能找到的唯一的问题是在您创建结果列表的末尾：

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

这将始终在NullPointerException因为get()预期的关键，你的情况结果，这是一个String，而不是int。遍历地图使用类似

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()); 
    }  
} 

此外，我想你wan't从from到to返回实际的路径，所以你需要一个getter添加getFrån()到DijkstraObjekt，然后建立列表像这个：

String fromNode = samling.get(to).getNode(); 
    djikstaList.add(to); 
    while(fromNode != from){ 
     fromNode = samling.get(fromNode).getFrån(); 
     djikstaList.add(fromNode); 
    } 

在此之后，列表将包含相反顺序的完整路径（包括开始和结束节点）。

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

干杯 tannerli

Answer 2

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

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

编辑：

对不起，我认为{}在那里。那里一切都很好。我会继续寻找。

Answer 3

也许试试这个：

if(currentNode==null || currentNode.getAktuell() == null) 
     break;   
if(currentNode.getAktuell())    
     continue;