Кратчайший путь с использованием алгоритма Дейкстры - PullRequest
8 голосов
/ 05 июля 2011

В настоящее время я реанимирую старое домашнее задание, в котором я пишу программу, которая среди других функций включает в себя поиск кратчайшего пути в графе с использованием алгоритма Дейкстры.

Я думаю, что по большей части я правильно понял, но я продолжаю получать NullPointerException в строке 58 при выполнении if(currentNode.getAktuell()).

Я пробовал несколько решений назад ивперед, но не могу понять, что не так, но 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;
    }

Ответы [ 3 ]

3 голосов
/ 05 августа 2011

Я не смог восстановить исключение NullPointerException, о котором вы нам рассказали. Как отметил Леандро, проблема может заключаться в вашей реализации 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());
    }       
}

Кроме того, я предполагаю, что вы не хотите возвращать фактический путь от from до to, поэтому вам нужно будет добавить получатель 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

0 голосов
/ 05 июля 2011

Может быть попробовать это:

if(currentNode==null || currentNode.getAktuell() == null)
         break;        
if(currentNode.getAktuell())            
        continue;
0 голосов
/ 05 июля 2011

Я думаю, что это может быть проблемой:

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

EDIT:

Извините, я думал, что {} есть. Там все в порядке. Я буду продолжать искать.

...