ruta más corta utilizando el algoritmo de Dijkstra

Question

Actualmente estoy revivir una vieja asignación de tareas, donde estoy escribiendo un programa que entre otras funciones, consiste en encontrar el camino más corto en un gráfico usando el algoritmo de Dijkstra.

Creo que lo tengo correcto en su mayor parte, pero sigo recibiendo NullPointerException en la línea 58 al ejecutar if(currentNode.getAktuell()).

He estado probando varias soluciones hacia adelante y hacia atrás, pero parece que no puedo encontrar lo que está mal, pero prioQueue.poll(); devuelve null cuando la cola está vacía. Intenté manejar el último currentNode que eventualmente se convierte en nulo pero no he podido encontrar una solución funcional, así que estoy empezando a pensar que he perdido algo aquí.

Realmente apreciaría si alguien familiarizado con Dijkstras algoritmo me podría ayudar aquí. Probablemente haya una mejor solución para el algoritmo, pero solo quiero ayuda para descubrir qué está mal con la que he escrito, y no "la respuesta" usando el algoritmo de otra persona.

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

Heres mi clase 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; 
    } 
} 

Estos deberían ser los métodos relevent de mi clase 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

no pude reconstruir la NullPointerException que nos hablaste. Como señaló Leandro, el problema podría ser la implementación de ListEdge y Graph.

lo hice una implementación de ambas clases a mí mismo para probar el código.

El único problema que encontramos fue en el extremo donde se crea la lista de resultados:

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

Esto siempre dará como resultado una NullPointerException porque get() espera una llave y en su caso que es un String, no una int. Para iterar sobre el uso Mapa algo así como

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

Además, supongo que wa no para devolver la trayectoria real de from a to lo que sería necesario añadir un captador getFrån() a DijkstraObjekt y luego construir la lista como esto:

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

Después de esto, la Lista contendrá la ruta completa (incluidos los nodos de Inicio y Fin) en orden inverso.

Si lo desea, puedo publicar todas mis clases que utilicé para probar/depurar.

Saludos tannerli

Answer 2

Creo que esto podría ser un problema:

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

EDITAR:

momento pensé que el {} está allí. Todo está bien allí. Seguiré buscando.

Answer 3

Tal vez intente esto:

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