Dijkstra Algorithmus funktioniert nicht

[schleo13]

Ich habe den Dijkstra Algorithmus implementiert und der letzte Wert in der Queue wird nicht
bearbeitet. Ich weiß wirklich nicht woran es liegt.

 

[mihe7]

Ich seh da keine Implementierung nur

                //TODO  Add you code here

                return new ArrayList<>(); // dummy, replace

 

[schleo13]

package lab;

import java.util.ArrayList;
import java.util.PriorityQueue;

public class GR {
ArrayList<Node> NodesList = new ArrayList<Node>();
PriorityQueue<Node> QR = null;
ArrayList<Node> Pfad = new ArrayList<Node>();

public GR(ArrayList<Node> N) {
    this.NodesList = N;
}

public PriorityQueue<Node> getQ(){
    return this.QR;
}
public void init(ArrayList<Node> NListe, Node Start) {
    for(Node N: NListe) {
        N.setDistanz(Double.POSITIVE_INFINITY);
        N.setVorgänger(null);
    }
    Start.setDistanz(0);
    this.QR = new PriorityQueue<Node>(NListe.size(), new Compi());
    QR.addAll(NListe);
}

public double distanzUp(Node u, Node v) {
    double alt = 0;
    alt =   u.getDistanz() + u.getStrecke(v);
    if(alt < v.getDistanz()) {
        v.setDistanz(alt);
        v.setVorgänger(u);
       
    }
    return alt;
}

public void Dijktstra(ArrayList<Node> gr, Node start) {
    init(gr, start);
   
    while(getQ().isEmpty() != true ) {
       
        Node u = getQ().poll();
        for(Node v : u.getNachbarn()) {
                distanzUp(u, v);   
        }}
   
   
}



public Node searchNode(ArrayList<Node> NL, String s) {
    for(Node n : NL) {
        if(n.Name.equals(s)) {
            return n;
        }
    }
    return null;}

public ArrayList<String> getKürzesteRoute(ArrayList<String> A, ArrayList<String>B, ArrayList<String> Data){
    String s = "[style=bold]";
    ArrayList<String> as = new ArrayList<String>();
    for(int i = 0; i <= Data.size()-1; i++) {
        for(int u = 0; u <= A.size()-1; u++)
        if(Data.get(i).contains(A.get(u)) && Data.get(i).contains(B.get(u))) {
            StringBuilder sb = new StringBuilder();
            sb.append(Data.get(i));
            sb.append(s);
            String sa = sb.toString();
            as.add(sa);
        }
        as.add(Data.get(i));
    }
    return as;
}

 

[schleo13]

package lab;

import java.util.ArrayList;

public class Node {
String Name = null;
double Zeit = 0;

ArrayList<Edge> EdgesList =  new ArrayList<Edge>();
double Distanz = 0;
Node Vorgänger = null;
double ZeitAllg = 0;

public Node(String na, double d) {
    this.Name = na;
    this.Zeit = d;
}



public void setEdges(Edge e){
    this.EdgesList.add(e);
}
public ArrayList<Edge> getEdges(){
    return this.EdgesList;
}
public void setZeitAllg(int i ) {
    this.ZeitAllg = i;
}
public double getZeitAllg() {
    return this.ZeitAllg;
}
public void setDistanz(double alt) {
    this.Distanz = alt;
}
public double getDistanz() {
    return this.Distanz;
}
public void setVorgänger(Node n) {
    this.Vorgänger = n;
}
public Node getVorgänger() {
    return this.Vorgänger;
}
public ArrayList<Node> getNachbarn(){
    ArrayList<Node> Nachbarn = new ArrayList<Node>();
    for(Edge k : getEdges()) {
        Nachbarn.add(k.Ziel);
    }
    return Nachbarn;
}
public double getStrecke( Node v) {
    for(Edge k : getEdges()) {
        if(k.Ziel.Name.equals(v.Name)) {
            return k.Gewicht;
        }
    }
    return -500;
}



}

 

[schleo13]

package lab;

import java.util.Comparator;

public class Compi implements Comparator<Node> {
   

    @Override
    public int compare(Node o1, Node o2) {
        if(o1.getDistanz() < o2.getDistanz()) {
        return -1;}
        if(o1.getDistanz() > o2.getDistanz()) {
            return 1;}
        else return 0;
       
    }
}