Created
February 24, 2015 18:02
-
-
Save heckenmann/6a42de6413efa815dff0 to your computer and use it in GitHub Desktop.
Dijkstra-Algorithmus
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// 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(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
//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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment