Dijkstra-Algorithmus

DijkstraImpl.java

 //
 // Implementierung des Dijkstra-Algorithmus.
 //
package dijkstraimpl;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
 //
 //
 //@author heckenmann.de
 //
public class DijkstraImpl {
 
    private final Knoten startpunkt;
    private final Knoten zielpunkt;
    private final List<Knoten> prioListe; // Knoten sortiert nach Entfernung
 
     //
     //Konstruktor. Achtung! Die Klasse verändert die Werte in den übergebenen
     //Knoten.
     //
     //@param startpunkt Startpunkt im Graph
     //@param zielpunkt Zielpunkt im Graph
     //
    public DijkstraImpl(final Knoten startpunkt, final Knoten zielpunkt) {
        this.startpunkt = startpunkt;
        this.zielpunkt = zielpunkt;
        this.prioListe = new ArrayList<>();
        sucheWeg();
    }
 
     //
     //Sucht den kürzestens Weg zum Zielpunkt.
     //
    private void sucheWeg() {
        this.prioListe.add(this.startpunkt);
         
        while (!this.prioListe.isEmpty()) {
            this.berechneNaechsteKnoten(this.prioListe.get(0));
        }
    }
 
     //
     //Hilfsmethode für die Methode sucheWeg.
     //
    private void berechneNaechsteKnoten(final Knoten aktuellerKnoten) {
        System.out.println(aktuellerKnoten.getName() + ": " + aktuellerKnoten.berechneEntfernungRekursiv());
        // Aus der Prioliste entfernen
        this.prioListe.remove(aktuellerKnoten);
         
        // Falls es sich um den Zielpunkt handelt, wird abgebrochen
        if(aktuellerKnoten.equals(this.zielpunkt)) {
            return;
        }
 
        // Die Nachbarn nach Entfernung sortieren.
        List<Knoten> kReihenfolge = new ArrayList<>();
        kReihenfolge.addAll(aktuellerKnoten.getNachbarn());
        kReihenfolge.remove(aktuellerKnoten.getVorgaenger());
        Collections.sort(kReihenfolge);
 
        // Jeden direkten Nachbar durchlaufen.
        for (Knoten aktuellerNachbar: kReihenfolge) {
            // Für jeden Nachbar den Vorgänger setzen, falls eine kürzere Route gefunden wurde.
            double distanz = aktuellerKnoten.distance(aktuellerNachbar);
            if (aktuellerNachbar.berechneEntfernungRekursiv() > aktuellerKnoten.berechneEntfernungRekursiv() + distanz
                    || aktuellerNachbar.berechneEntfernungRekursiv() == -1) {
                aktuellerNachbar.setVorgaenger(aktuellerKnoten);
            }
 
            // Falls der aktuelleNachbar NICHT in der Prioliste vorhanden ist, wird er hinzugefügt.
            if (!this.prioListe.contains(aktuellerNachbar)) {
                this.prioListe.add(aktuellerNachbar);
            }
            Collections.sort(this.prioListe); // ...muss trotzdem ausgeführt werden, weil sich die Entfernung geändert haben kann.
        }
    }
     
     //
     //Gibt die Reihenfolge der Knoten zurück.
     //@return Reihenfolge der Knoten des kürzestens Weges.
     //
    public List<Knoten> getErgebnisReihenfolge() {
        List<Knoten> er = new ArrayList<>();
        for(Knoten k = zielpunkt; k != null; k = k.getVorgaenger()) {
            er.add(0, k);
        }
        return er;
    }
 
     //
     //Gibt die minimale Entfernung zurück.
     //
     //@return Minimale Entfernung
     //
    public double getMinimaleEntfernung() {
        return this.zielpunkt.berechneEntfernungRekursiv();
    }
}

DijkstraTest.java

//
 //JUnit-Test für DijkstraImpl
 //
 
import dijkstraimpl.Knoten;
import org.junit.Test;
import dijkstraimpl.DijkstraImpl;
import static org.junit.Assert.*;
 
 //
 //
 //@author heckenmann.de
 //
public class DijkstraTest {
     
     //
     //Graph von Wikipedia.
     //
    @Test
    public void test1() {
        // Koordinaten von http://www.fwiegleb.de/geo-a.htm
        Knoten frankfurt = new Knoten("Frankfurt", 50117, 8683, true, false);
        Knoten mannheim = new Knoten("Mannheim", 49483, 8467, false, false);
        Knoten wuerzburg = new Knoten("Würzburg", 49800, 9933, false, false);
        Knoten kassel = new Knoten("Kassel", 51317, 9500, false, false);
        Knoten karlsruhe = new Knoten("Karlsruhe", 49017, 8400, false, false);
        Knoten erfurt = new Knoten("Erfurt", 50986, 11022, false, false);
        Knoten nuernberg = new Knoten("Nürnberg", 49450, 11083, false, false);
        Knoten stuttgart = new Knoten("Stuttgart", 48783, 9183, false, false);
        Knoten augsburg = new Knoten("Augsburg", 48367, 10900, false, false);
        Knoten muenchen = new Knoten("München", 48133, 11567, false, true);
         
        frankfurt.addNachbar(mannheim);
        frankfurt.addNachbar(wuerzburg);
        frankfurt.addNachbar(kassel);
         
        mannheim.addNachbar(karlsruhe);
         
        wuerzburg.addNachbar(erfurt);
        wuerzburg.addNachbar(nuernberg);
         
        nuernberg.addNachbar(stuttgart);
        nuernberg.addNachbar(muenchen);
         
        kassel.addNachbar(muenchen);
         
        karlsruhe.addNachbar(augsburg);
         
        augsburg.addNachbar(muenchen);
         
        DijkstraImpl d = new DijkstraImpl(frankfurt, muenchen);
        System.out.println("Berechnete Entfernung: "  + d.getMinimaleEntfernung());
        for(Knoten k: d.getErgebnisReihenfolge()) {
            System.out.println(k.getName());
        }
         
        // Laut Wikipedia ist die kürzeste Route Frankfurt - Würzburg - Nürnberg - München
        double distanz = frankfurt.distance(wuerzburg) + wuerzburg.distance(nuernberg) + nuernberg.distance(muenchen);
 
        assertEquals(distanz, d.getMinimaleEntfernung(), 0);
    }
}

Knoten.java

package dijkstraimpl;
 
 //
 //Stellt einen Knoten dar.
 //
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
 
 //
 //@author heckenmann.de
 //
public class Knoten extends Point implements Comparable {
 
     //
     //Name des Knoten
     //
    private final String name;
 
     //
     //Knoten, die direkt über eine Kante mit diesem Knoten verbunden sind.
     //
    private final List<Knoten> nachbarn;
 
     //
     //Vorgänger
     //
    private Knoten vorgaenger;
 
     //
     //Legt fest, ob der Knoten der Startpunkt ist.
     //
    private final boolean startpunkt;
 
     //
     //Legt fest, ob der Knoten der Zielpunkt ist.
     //
    private final boolean zielpunkt;
 
     //
     //Konstruktor.
     //
     //@param name Name des Knoten
     //@param x x-Position
     //@param y y-Position
     //@param startpunkt Legt diesen Knoten als Startpunkt fest
     //@param zielpunkt Legt diesen Knoten als Zielpunkt fest
     //
    public Knoten(final String name, final int x, final int y, final boolean startpunkt, final boolean zielpunkt) {
        super(x, y);
        this.name = name;
        this.startpunkt = startpunkt;
        this.zielpunkt = zielpunkt;
        this.nachbarn = new ArrayList<>();
    }
 
     //
     //Fügt diesem Knoten einen Nachbarn hinzu und fügt dem Nachbarn diesen
     //Knoten als Nachbar hinzu.
     //
     //@param nachbar Der neue Nachbarknoten. Darf nicht null sein!
     //
    public void addNachbar(final Knoten nachbar) {
        // Nachbar hinzufügen
        if (!this.nachbarn.contains(nachbar)) {
            this.nachbarn.add(nachbar);
        }
        // Diesen Knoten als Nachbar hinzufügen
        if (!nachbar.isNachbar(this)) {
            nachbar.addNachbar(this);
        }
    }
 
     //
     //Prüft, ob der übergebene Knoten ein Nachbar ist.
     //
     //@param k Zu prüfender Nachbar.
     //@return True, wenn der übergebene Knoten ein Nachbar ist.
     //
    public boolean isNachbar(final Knoten k) {
        return this.nachbarn.contains(k);
    }
 
     //
     //Gibt die Nachbarn zurück.
     //
     //@return Liste der Nachbarn
     //
    public List<Knoten> getNachbarn() {
        return nachbarn;
    }
 
     //
     //Gibt den Vorgänger zurück.
     //
     //@return Vorgänger
     //
    public Knoten getVorgaenger() {
        return this.vorgaenger;
    }
 
     //
     //Setzt den Vorgänger.
     //
     //@param vorgaenger Vorgänger
     //
    public void setVorgaenger(Knoten vorgaenger) {
        this.vorgaenger = vorgaenger;
    }
 
     //
     //Berechnet die Entfernung zum Startpunkt. Wird verwendet anstatt einer
     //statisch gesetzten Entfernung.
     //
     //@return Entfernung zum Startpunkt. -1 falls keine Route zum Startpunkt
     //existiert.
     //
    public double berechneEntfernungRekursiv() {
        double entfernung = 0;
        if (this.vorgaenger != null) {
            entfernung += vorgaenger.distance(this);
 
            double entfernungVorgaenger = vorgaenger.berechneEntfernungRekursiv();
            // Falls momentan keine Route bis zum Startpunkt existiert, wird -1 zurückgegeben
            if (entfernungVorgaenger != -1) {
                entfernung += entfernungVorgaenger;
            } else {
                entfernung = entfernungVorgaenger;
            }
 
        } else if (!this.startpunkt) {
            // Kein Vorgänger und kein Startpunkt
            entfernung = -1;
        } else {
            // Es handelt sich um den Startpunkt
            entfernung = 0;
        }
        return entfernung;
    }
 
    @Override
    public int compareTo(Object o) {
        // NullPointerException und ClassCastException dürfen von der Methode geworfen werden
        Knoten k = (Knoten) o;
        double differenz = this.berechneEntfernungRekursiv() - k.berechneEntfernungRekursiv();
        if (differenz == 0) {
            return 0;
        } else if (differenz > 0) {
            return 1;
        } else {
            return -1;
        }
    }
 
     //
     //Gibt den Namen zurück.
     //
     //@return
     //
    public String getName() {
        return this.name;
    }
}