Dijkstra-Algorithmus - Versionsgeschichte

Akaibel am 23. Januar 2022 um 17:00 Uhr

2022-01-23T17:00:18Z

← Nächstältere Version		Version vom 23. Januar 2022, 17:00 Uhr
Zeile 74:		Zeile 74:
	<b>Klasse <code>DijkstraTest</code>:</b>		<b>Klasse <code>DijkstraTest</code>:</b>

	<code>		<code>
	package _test;		package _test;

Zeile 245:		Zeile 245:
	}		}
	}		}
	</code>		</code>


Zeile 251:		Zeile 251:
	<b>Klasse <code>DijkstraInfo</code>:</b>		<b>Klasse <code>DijkstraInfo</code>:</b>

	<code>		<code>
	package graph;		package graph;

Zeile 286:		Zeile 286:
	}		}

	public String toString() {		public String toString() {
	if(vorgaenger != null){		if(vorgaenger != null){
	return vertex.getID() + ", " + distanz + ", Vorg.: " + vorgaenger.getID();		return vertex.getID() + ", " + distanz + ", Vorg.: " + vorgaenger.getID();
Zeile 295:		Zeile 295:
	}		}
	}		}
			</code>
	</code>

Akaibel: /* Implementierung */

2019-09-28T08:10:54Z

Implementierung

← Nächstältere Version		Version vom 28. September 2019, 08:10 Uhr
Zeile 95:		Zeile 95:

	'''public List<DijkstraInfo> dijkstraAlgorithmus(String sStart)'''{		'''public List<DijkstraInfo> dijkstraAlgorithmus(String sStart)'''{
	roteListe = new ListWithViewer<DijkstraInfo>();		roteListe = new ListWithViewer<DijkstraInfo>();
	gelbeListe = new ListWithViewer<DijkstraInfo>();		gelbeListe = new ListWithViewer<DijkstraInfo>();
	Vertex vStart = graph.getVertex(sStart);		Vertex vStart = graph.getVertex(sStart);
	DijkstraInfo dStart = new DijkstraInfo(vStart,0,null);		DijkstraInfo dStart = new DijkstraInfo(vStart,0,null);
	dStart.setDistanz(0);		dStart.setDistanz(0);
	gelbeListe.append(dStart);		gelbeListe.append(dStart);
	~~//TODO~~		while(! gelbeListe.isEmpty()){
	while(! gelbeListe.isEmpty()){		gelbeListe.toFirst();
	gelbeListe.toFirst();		DijkstraInfo neuerRoterDI = gelbeListe.getContent();
	DijkstraInfo neuerRoterDI = gelbeListe.getContent();		gelbeListe.remove();
	gelbeListe.remove();		roteListe.append(neuerRoterDI);
	roteListe.append(neuerRoterDI);		Vertex neuerRoterV = neuerRoterDI.getVertex();
	Vertex neuerRoterV = neuerRoterDI.getVertex();		neuerRoterV.setMark(true);
	neuerRoterV.setMark(true);		double distanzBisNeuerRoter = neuerRoterDI.getDistanz();
	double distanzBisNeuerRoter = neuerRoterDI.getDistanz();		List<Vertex> nachbarn = graph.getNeighbours(neuerRoterV);
	List<Vertex> nachbarn = graph.getNeighbours(neuerRoterV);		for(nachbarn.toFirst();nachbarn.hasAccess();nachbarn.next()){
	for(nachbarn.toFirst();nachbarn.hasAccess();nachbarn.next()){		Vertex nachbarV = nachbarn.getContent();
	Vertex nachbarV = nachbarn.getContent();		if(! nachbarV.isMarked()){
	if(! nachbarV.isMarked()){		Edge e = graph.getEdge(neuerRoterV, nachbarV);
	Edge e = graph.getEdge(neuerRoterV, nachbarV);		DijkstraInfo neuDI = new DijkstraInfo(nachbarV,distanzBisNeuerRoter+e.getWeight(),neuerRoterV);
	DijkstraInfo neuDI = new DijkstraInfo(nachbarV,distanzBisNeuerRoter+e.getWeight(),~~neuerRoterDI~~);		inGelbeListeUpdaten(neuDI);
	inGelbeListeUpdaten(neuDI);		}
	}		}
	}		}
	}		return roteListe;
	return roteListe;
	}		}

Zeile 257:		Zeile 256:
	public class DijkstraInfo{		public class DijkstraInfo{

	private Vertex vertex;		private Vertex vertex;
	private double distanz;		private double distanz;
	private ~~DijkstraInfo~~ vorgaenger;		private Vertex vorgaenger;

	public DijkstraInfo(Vertex pVertex, double pDistanz, ~~DijkstraInfo~~ pVorgaenger){		public DijkstraInfo(Vertex pVertex, double pDistanz, Vertex pVorgaenger){
	this.vertex = pVertex;		this.vertex = pVertex;
	this.distanz = pDistanz;		this.distanz = pDistanz;
	this.vorgaenger = pVorgaenger;		this.vorgaenger = pVorgaenger;
	}		}

			public Vertex getVertex(){
			return vertex;
			}

	~~public Vertex getVertex(){~~		public double getDistanz() {
	~~return vertex;~~		return distanz;
	}		}

	public double getDistanz() {
	return distanz;
	}

	public void setDistanz(double distanz) {		public void setDistanz(double distanz) {
	this.distanz = distanz;		this.distanz = distanz;
	}		}

	public ~~DijkstraInfo~~ getVorgaenger() {		public Vertex getVorgaenger() {
	return vorgaenger;		return vorgaenger;
	}		}

	public void setVorgaenger(~~DijkstraInfo~~ vorgaenger) {		public void setVorgaenger(Vertex vorgaenger) {
	this.vorgaenger = vorgaenger;		this.vorgaenger = vorgaenger;
	}		}

	public String toString() {		public String toString() {
	if(vorgaenger != null){		if(vorgaenger != null){
	return vertex.getID() + ", " + distanz + ", Vorg.: " + vorgaenger~~.getVertex()~~.getID();		return vertex.getID() + ", " + distanz + ", Vorg.: " + vorgaenger.getID();
	}		}
	else{		else{
	return vertex.getID() + ", " + distanz + ", Vorg.: ---";		return vertex.getID() + ", " + distanz + ", Vorg.: ---";
	}		}
			}
	}
	}		}

	</code>		</code>

Akaibel: /* Implementierung */

2019-09-27T16:26:27Z

Implementierung

Änderungen zeigen

Akaibel am 23. Juni 2019 um 13:27 Uhr

2019-06-23T13:27:42Z

← Nächstältere Version		Version vom 23. Juni 2019, 13:27 Uhr
Zeile 11:		Zeile 11:

	Der Dijkstra-Algorithmus bezieht sich auf die Datenstruktur [[Graph]].		Der Dijkstra-Algorithmus bezieht sich auf die Datenstruktur [[Graph]].
			=Fachbegriffe=

			Dijkstra-Algorithmus, rote Liste, gelbe Liste

	= Idee des Dijkstra-Algorithmus=		= Idee des Dijkstra-Algorithmus=

Akaibel: Akaibel verschob die Seite Dijkstra-Algorithmus ab Abi 2017 nach Dijkstra-Algorithmus

2018-09-03T06:31:46Z

Akaibel verschob die Seite Dijkstra-Algorithmus ab Abi 2017 nach Dijkstra-Algorithmus

← Nächstältere Version	Version vom 3. September 2018, 06:31 Uhr
(kein Unterschied)

Mgrifka: /* Implementierung */

2016-08-11T07:02:46Z

Implementierung

← Nächstältere Version		Version vom 11. August 2016, 07:02 Uhr
Zeile 252:		Zeile 252:


	<b>Klasse <code>~~DijktstraNode~~</code>:</b>		<b>Klasse <code>DijkstraNode</code>:</b>

	<code>		<code>

Mgrifka: Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-Abitur Kategorie:Datenstrukturen(IF) 400px [[File:De…“

2016-08-11T07:01:47Z

Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Informatik-Abitur Kategorie:Datenstrukturen(IF) thumb|Originalgraph |400px [[File:De…“

Neue Seite

[[Kategorie:Informatik]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Datenstrukturen(IF)]]

[[File:Deutschland-graph.png|thumb|Originalgraph |400px]]
[[File:Deutschland-graph-dijkstra-kassel.png|thumb|Ergebnis des Dijkstra-Algorithmus für Kassel |400px]]

Mit Hilfe des Dijkstra-Algorithmus kann man für einen Startknoten die kürzesten Wege zu allen anderen Knoten des Graphen bestimmen.

Der Dijkstra-Algorithmus ist wesentlich effizienter als die Suche nach einem kürzesten Weg mithilfe von [[Backtracking ab Abi 2017|Backtracking]]

Der Dijkstra-Algorithmus bezieht sich auf die Datenstruktur [[Graph]].

= Idee des Dijkstra-Algorithmus=
==Notwendige Datenstrukturen==
* Für jeden Knoten wird der Vorgänger und ein Wert <code>distanz</code> gespeichert; <code>distanz</code> gibt die bisher beste gefundene Distanz zum Startknoten an.
* '''gelbe Liste''': In dieser Liste werden Knoten gespeichert, für die schon ein Distanzwert vorliegt, deren Distanz zum Startknoten aber noch nicht abschließend festgelegt werden konnte. Die Knoten erscheinen in der gelben Liste gemäß ihrem Distanzwert, und zwar in aufsteigender Reihenfolge.
* '''rote Liste''': Man braucht eine Liste, in der alle Knoten gespeichert werden, deren Distanz zum Startknoten abschließend festgestellt wurde.

==Algorithmus==
# Die Distanz des Startknoten wird auf 0 gesetzt; der von allen anderen Knoten auf unendlich.
# Der Startknoten wird in die rote Liste eingefügt.
# Alle Nachbarknoten des Startknotens werden in die gelbe Liste eingefügt, und zwar gemäß ihrer Distanz zum Startknoten.
# Die folgenden Schritte laufen jetzt so lange, bis die gelbe Liste leer ist:
## den ersten Knoten aus der gelben Liste (im folgenden <code>ersterGelber</code>) entnehmen und in die rote Liste einfügen. Denn die Distanz dieses Knotens ist endgültig geklärt.
## für alle Nachbarknoten von <code>ersterGelber</code> überprüft man:
### wenn sie noch nicht in der gelben Liste sind: Distanz berechnen (=Distanz von <code>ersterGelber</code> plus Kantenlänge von <code>ersterGelber</code>) und dann in die gelbe Liste hinzufügen (=gemäß der Distanz einfügen)
### wenn sie schon in der gelben Liste sind: Überprüfen, ob die Distanz von <code>ersterGelber</code> plus Kantenlänge '''kleiner''' ist als die bisher gespeicherte Distanz: Dann hat man eine bessere Route gefunden! Die Distanz des Nachbarknoten wird dann entsprechend verbessert, wodurch sich seine Position in der gelben Liste verbessert.

==Kürzester Weg für einen beliebigen Knoten==
Die Distanz kann man direkt aus dem Knoten auslesen.

Den kürzesten Weg von einem beliebigen Knoten zum Startknoten kann man jetzt angeben, indem man sich von dem Knoten aus immer zum nächsten Vorgänger hangelt, bis mn schließlich beim Startknoten angekommen ist.

== Beispiel ==
Für den Startknoten Kassel sind die ersten Schritte des Dijkstra-Algorithmus die folgenden.

* Die '''rote Liste''' ist '''fett'' geschrieben und ist von oben nach unten zu lesen.
* Die '''gelbe Liste''' ist jeweils von links nach rechts zu lesen.
** Veränderungen in der gelben Liste sind unterstrichen.
In der gelben Liste wird in Klammern die aktuelle Distanz zum Startknoten und der Vorgängerknoten (als Nummernschild) angegeben.
* '''Kassel (0, --)''': Dortmund (160, KS), Hannover (167, KS), Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS)
* '''Dortmund (160, KS)''': Hannover (167, KS), Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (394, DO)
* '''Hannover (167, KS)''': Frankfurt (193, KS), Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Berlin (457, H)
* '''Frankfurt (193, KS)''': Wuerzburg (209, KS), Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Karlsruhe (340, F), Berlin (457, H)
* '''Wuerzburg (209, KS)''': Leipzig (250, KS), Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (457, H)
* '''Leipzig (250, KS)''': Koeln (253, DO), Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Berlin (438, L)
* '''Koeln (253, DO)''': Bremen (289, H), Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
* '''Bremen (289, H)''': Hamburg (317, H), Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
* '''Hamburg (317, H)''': Nuernberg (319, WÜ), Karlsruhe (340, F), Berlin (438, L)
* '''Nuernberg (319, WÜ)''': Karlsruhe (340, F), Berlin (438, L), Muenchen (485, N), Stuttgart (527, N)
* '''Karlsruhe (340, F)''': Stuttgart (422, KA), Berlin (438, L), Muenchen (485, N)
* '''Stuttgart (422, KA)''': Berlin (438, L), Muenchen (485, N)
* '''Berlin (438, L)''': Muenchen (485, N)
* '''Muenchen (485, N)'''

Den kürzesten Weg von Kassel nach Stuttgart findet man jetzt, indem man in der roten Liste Stuttgart sucht und dann in der roten Liste "rückwärts" geht:

Stuttgart (422, KA) -> Karlsruhe (340, F) -> Frankfurt (193, KS) -> Kassel (0, --)

= Implementierung =
Diese Implementierung umfasst zwei Klassen:
* <code>DijkstraAlgorithmus</code>
* <code>DijkstraNode</code>
Die Klasse <code>DijkstraAlgorithmus</code> enthält eine (lange...) Methode <code>initGraph</code>, damit man das Ganze auch testen kann.

Klasse <code>DijkstraAlgorithmus</code>:

<code>
import graph.Graph;
import graph.GraphWithViewer;
import gui.GUI;
import linear.List;
import linear.ListWithViewer;

'''public class DijkstraAlgorithmus {'''
public GraphWithViewer graph;
List<DijkstraNode> gelbeListe;
List<DijkstraNode> roteListe;

'''public DijkstraAlgorithmus(){'''
initGraph();
}

'''public void dijkstra(String pStadt) {'''
gelbeListe = new ListWithViewer<>();
roteListe = new ListWithViewer<>();
DijkstraNode startNode = (DijkstraNode)graph.getNode(pStadt);
startNode.setDistanz(0);
gelbeListe.append(startNode);
while(!gelbeListe.isEmpty()){
gelbeListe.toFirst();
DijkstraNode ersterGelber = gelbeListe.getContent();
//System.out.println("ersterGelber: "+ersterGelber);
gelbeListe.remove();
ersterGelber.mark();
roteListe.append(ersterGelber);
List<GraphNode> nachbarn = graph.getNeighbours(ersterGelber);
nachbarn.toFirst();
while(nachbarn.hasAccess()){
DijkstraNode derNachbar = (DijkstraNode) nachbarn.getContent();
if (!derNachbar.isMarked()) {
//System.out.println("currentNeighbour: "+currentNeighbour);
double streckeErsterZumNachbar = graph.getEdgeWeight(ersterGelber, derNachbar);
if (ersterGelber.getDistanz() + streckeErsterZumNachbar < derNachbar.getDistanz()) {
// ueber derNachbar fuehrt eine kuerzere Strecke zu currentNeighbour!
derNachbar.setVorgaenger(ersterGelber);
derNachbar.setDistanz(ersterGelber.getDistanz() + streckeErsterZumNachbar);
inGelbeListeUpdaten(derNachbar);
}
}
nachbarn.next();
}
}
}

/**
* sorgt dafuer, dass node gemaess seiner Distanz
* die richtige Position in gelbeListe bekommt.
* wenn pNode noch gar nicht in gelbeListe enthalten ist,
* dann wird node an der richtigen Stelle eingefuegt.
*/
'''private void inGelbeListeUpdaten(DijkstraNode pNode) {'''
boolean inserted = false;
gelbeListe.toFirst();
while(gelbeListe.hasAccess()){
DijkstraNode aktuell = gelbeListe.getContent();
if(aktuell.getDistanz() >= pNode.getDistanz()){
gelbeListe.insert(pNode);
inserted = true;
break;
}
gelbeListe.next();
}
if(inserted){
// ggf. taucht pNode nochmal in der Liste auf!
// dann muss er entfernt werden!
while(gelbeListe.hasAccess()){
DijkstraNode aktuell = gelbeListe.getContent();
if(aktuell.getName().equals(pNode.getName())){
gelbeListe.remove();
break;
}
gelbeListe.next();
}
}
else{
// der Knoten wurde noch nicht eingefuegt!
gelbeListe.append(pNode);
}
}

/**
* erzeugt einen Graph, in dem nur die Dijkstra-Verbindungen eingetragen sind
* @param pGraph
* @param roteListe
* @return
*/
'''public GraphWithViewer zeigeDijkstraGraph(){'''
Graph pGraph = graph;
GraphWithViewer ergebnis = new GraphWithViewer();
List<GraphNode> nodes = pGraph.getNodes();
for(nodes.toFirst(); nodes.hasAccess(); nodes.next()){
ergebnis.addNode((DijkstraNode) nodes.getContent());
}
for(roteListe.toFirst(); roteListe.hasAccess(); roteListe.next()){
DijkstraNode aktuell = roteListe.getContent();
DijkstraNode vorgaenger = aktuell.getVorgaenger();
if(vorgaenger != null){
double distanz = pGraph.getEdgeWeight(pGraph.getNode(aktuell.getName()), pGraph.getNode(vorgaenger.getName()));
ergebnis.addEdge(ergebnis.getNode(aktuell.getName()),
ergebnis.getNode(vorgaenger.getName()),
distanz);
}
}
ergebnis.switchToISOMLayout();
return ergebnis;
}

'''private void initGraph(){'''
graph = new GraphWithViewer();

DijkstraNode dortmund = new DijkstraNode("Dortmund");
graph.addNode(dortmund);
DijkstraNode koeln = new DijkstraNode("Koeln");
graph.addNode(koeln);
DijkstraNode frankfurt = new DijkstraNode("Frankfurt");
graph.addNode(frankfurt);
DijkstraNode kassel = new DijkstraNode("Kassel");
graph.addNode(kassel);
DijkstraNode wuerzburg = new DijkstraNode("Wuerzburg");
graph.addNode(wuerzburg);
DijkstraNode bielefeld = new DijkstraNode("Bielefeld");
DijkstraNode hamburg = new DijkstraNode("Hamburg");
graph.addNode(hamburg);
DijkstraNode berlin = new DijkstraNode("Berlin");
graph.addNode(berlin);
DijkstraNode bremen = new DijkstraNode("Bremen");
graph.addNode(bremen);
DijkstraNode hannover = new DijkstraNode("Hannover");
graph.addNode(hannover);
DijkstraNode leipzig = new DijkstraNode("Leipzig");
graph.addNode(leipzig);
DijkstraNode nuernberg = new DijkstraNode("Nuernberg");
graph.addNode(nuernberg);
DijkstraNode stuttgart = new DijkstraNode("Stuttgart");
graph.addNode(stuttgart);
DijkstraNode muenchen = new DijkstraNode("Muenchen");
graph.addNode(muenchen);
DijkstraNode karlsruhe = new DijkstraNode("Karlsruhe");
graph.addNode(karlsruhe);

graph.addEdge(kassel, dortmund, 160);
graph.addEdge(dortmund, koeln, 93);
graph.addEdge(frankfurt, kassel, 193);
graph.addEdge(kassel, wuerzburg, 209);
graph.addEdge(wuerzburg, frankfurt, 119);
graph.addEdge(frankfurt, koeln, 189);
graph.addEdge(berlin, hamburg, 289);
graph.addEdge(hamburg, bremen, 119);
graph.addEdge(bremen, hannover, 122);
graph.addEdge(hannover, hamburg, 150);
graph.addEdge(berlin, hannover, 290);
graph.addEdge(berlin, leipzig, 188);
graph.addEdge(hannover, kassel, 167);
graph.addEdge(leipzig, kassel, 250);
graph.addEdge(dortmund, bremen, 234);
graph.addEdge(dortmund, hannover, 210);
graph.addEdge(leipzig, nuernberg, 278);
graph.addEdge(wuerzburg, nuernberg, 110);
graph.addEdge(nuernberg, muenchen, 166);
graph.addEdge(muenchen, stuttgart, 223);
graph.addEdge(nuernberg, stuttgart, 208);
graph.addEdge(stuttgart, karlsruhe, 82);
graph.addEdge(karlsruhe, frankfurt, 147);

// auf ein geeignetes Layout umstellen
graph.switchToISOMLayout();
}

'''public static void main(String[] args) {'''
DijkstraAlgorithmus da = new DijkstraAlgorithmus();
new GUI(da);
}
}
</code>

Klasse <code>DijktstraNode</code>:

<code>
import graph.GraphNode;

public class DijkstraNode extends GraphNode{

private DijkstraNode vorgaenger;
private double distanz;

public DijkstraNode(String pName) {
super(pName);
vorgaenger = null;
distanz = 100000000;
}

public void setDistanz(double pDistanz){
this.distanz = pDistanz;
}

public double getDistanz(){
return distanz;
}

public void setVorgaenger(DijkstraNode pNode){
this.vorgaenger = pNode;
}

public DijkstraNode getVorgaenger() {
return vorgaenger;
}

public String toString(){
String ergebnis = this.getName()+": "+this.distanz;
if(this.vorgaenger != null){
ergebnis += (" ("+vorgaenger.getName()+")");
}
return ergebnis;
}
}
</code>