Кратчайший путь с использованием алгоритма Дейкстры

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

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

Я пробовал несколько решений туда и обратно, но не могу понять, что не так, но prioQueue.poll(); возвращает null, когда очередь пуста. Я пытался обработать этот последний currentNode, который в конечном итоге превращается в ноль, но не смог найти работающее решение, поэтому я начинаю думать, что я что-то здесь упустил.

Я был бы очень признателен, если бы кто-то, знакомый с алгоритмом Дейкстры, мог помочь мне здесь. Вероятно, есть лучшее решение для алгоритма, но мне нужна только помощь в выяснении того, что не так с тем, что я написал, а не «ответ» с использованием чужого алгоритма.

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

person John Snow    schedule 05.07.2011    source источник
comment
Для нескандинавов vikt означает вес, från означает от, а aktuell означает текущий.   -  person Aasmund Eldhuset    schedule 05.07.2011
comment
да извините за это. У меня есть плохая привычка смешивать имена переменных/методов с английскими и шведскими :)   -  person John Snow    schedule 05.07.2011
comment
Пожалуйста, предоставьте нам свой код DijkstraObject или полную трассировку стека. Поскольку вы проверяете currentNode на null непосредственно перед этой строкой, NullPointerException должно происходить из метода getAktuell().   -  person Frank    schedule 06.07.2011
comment
Я включил класс DijkstraObject внизу страницы.   -  person John Snow    schedule 06.07.2011
comment
Если вы предоставите классы Graph и ListEdge, найти ошибку будет проще. Если вы еще не решили ее, отправьте эту информацию. Мне вот это интересно :)   -  person Leandro    schedule 02.08.2011
comment
Привет! Я добавил соответствующие методы в свой основной пост, который будет моим классом ListEdge, и соответствующие методы из графа. Пожалуйста, дайте мне знать, если вы можете узнать, что не так :)   -  person John Snow    schedule 05.08.2011


Ответы (3)


Я не смог восстановить исключение 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);
   }

После этого список будет содержать полный путь (включая начальный и конечный узлы) в обратном порядке.

При желании я могу опубликовать все свои классы, которые я использовал для тестирования/отладки.

Ура Таннерли

person tannerli    schedule 05.08.2011
comment
Привет! Я отредактировал свой основной пост, чтобы добавить недостающие методы из моего графика. Сейчас не дома, поэтому пока не могу попробовать ваш ответ, но я дам вам знать, если я смогу решить проблему с вашим ответом. - person John Snow; 05.08.2011
comment
Я не нашел ничего явно неправильного в этих двух добавленных вами классах (хотя было бы неплохо иметь весь класс ListGraph), я думаю, что проблема застряла в той части, которую я упомянул, потому что мне не пришлось ничего менять в логике самого алгоритма. для меня, чтобы заставить его работать. - person tannerli; 08.08.2011
comment
Спасибо за вашу помощь. Я сейчас в отпуске, но я попробую ваше предложение и отмечу его как решенное, если я заставлю его работать, как только вернусь домой, что будет через две недели :) - person John Snow; 08.08.2011
comment
У меня работает алгоритм. Как вы сказали, неправильно составлял список. Я также добавил, из какого узла вы пришли и каким образом, в класс djikstraObject. Спасибо большое, вы спасатель :) - person John Snow; 24.08.2011
comment
Всегда рад помочь, мне все равно пришлось готовиться к экзамену по структурам данных и алгоритмам :) - person tannerli; 25.08.2011

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

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

РЕДАКТИРОВАТЬ:

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

person Zoltan Balazs    schedule 05.07.2011

Может быть, попробуйте это:

if(currentNode==null || currentNode.getAktuell() == null)
         break;        
if(currentNode.getAktuell())            
        continue;
person Jason Rae    schedule 05.07.2011
comment
Я пробовал это раньше, но позже в коде это даст мне нулевой указатель. Думаю, я сделал что-то еще не так, но не могу понять, что это такое - person John Snow; 06.07.2011