Du würdest gerne wissen, welches der kürzeste Weg zwischen München und Rotterdam ist? Welche Flüge Du buchen solltest, um möglichst günstig von Berlin nach Sydney zu fliegen? Über welche Leitungen sich Dein Computer mit dem Server von www.studysmarter.de verbinden soll?
Dann könnte der Dijkstra Algorithmus für Dich hilfreich sein! Mit diesem Algorithmus kannst Du den kürzesten Weg von A nach B leicht bestimmen. Im Gegensatz zu anderen Greedy-Algorithmen berechnet der Dijkstra-Algorithmus jedoch immer die optimale Lösung.
Dijkstra Algorithmus Definition
1959 erfand der niederländische Mathematiker E. W. Dijkstra (ausgesprochen ˈdɛɪkˌstra) einen Algorithmus zum Finden kürzester Wege in gewichteten Graphen. Dieser Algorithmus ist mittlerweile in den meisten Routenplanern und Navigationsgeräten implementiert.
Abb. 1 – Edsger Wybe Dijkstra
Bei seinem Verfahren werden zunächst alle kürzesten Wege eines Teils des gesamten Graphen bestimmt. Dann vergrößert man den Untergraphen schrittweise und untersucht die Auswirkung dieses Wachstums auf den kürzesten Weg.
Dijkstras Algorithmus basiert auf einer iterativen Erweiterung einer Menge von "billig" erreichbaren Knoten und kann daher als eine auf dem Greedy-Prinzip basierende Weiterentwicklung der Breitensuche für gewichtete Kanten aufgefasst werden.
Dijkstras Idee: Wenn der kürzeste Pfad von A nach C durch B verläuft, dann ist das Pfadsegment zwischen A und B die kürzeste Verbindung zwischen diesen beiden Knoten.
Ein kleiner Hinweis für Dich: Du kannst den Dijkstra-Algorithmus nur verwenden, um die kürzesten oder billigsten Wege zu berechnen, solange alle Kosten positiv sind. Treten auch negative Zahlen auf, funktioniert der Algorithmus nicht mehr.
Welche Schreibweise ist richtig: "Dijkstra-Algorithmus" oder "Dijkstra Algorithmus". In der Praxis werden beide Varianten eingesetzt.
Dijkstra Algorithmus Anwendung
Damit hast Du den Einstieg der Erklärung geschafft. Und jetzt siehst Du, welche Idee hinter dem Dijkstra Algorithmus steckt und wie er funktioniert.
Die Grundidee des Dijkstra Algorithmus ist folgende: Kanten im naiven Algorithmus geschickt wählen!
Dijkstra Algorithmus – Pseudocode
Wie kann der Pseudocode beim Dijkstra Algorithmus aussehen? Der Algorithmus von Dijkstra berechnet die Kosten des billigsten Pfads vom Startknoten zu allen anderen Knoten im Graph.
Der Dijkstra-Algorithmus wählt Schritt für Schritt den aktuell günstigsten Pfad aus, ausgehend vom Startknoten und durch die nächsten erreichbaren Knoten. Er kann auch Verbesserungen vornehmen. Dies wird so lange durchgeführt, bis alle Knoten besucht wurden und keine besseren Pfade gefunden werden.
Um den Dijkstra-Algorithmus auszuführen, benötigt man eine Warteschlange. Dort werden alle gefundenen Knoten eingefügt. An der Spitze dieser Warteschlange steht der Knoten, zu dem aktuell die günstigste Route vom Ursprungsknoten führt.
algorithm dijkstra(s) {
input : Index s des Startknotens knoten[s]
output : speichert für jeden Knoten die Distanz und den Vorgänger auf einem kürzesten Weg von s
// Initialisiere Attribute aller Knoten:
for(i: 0 to n − 1) {
setze distanz von knoten[i] auf ∞;
setze vorgänger von knoten[i] auf null;
}
setze distanz von knoten[s] auf 0; // Distanz des Startknotens zu sich selbst
erzeuge PriorityQueue q mit allen Knoten;
// wende für den jeweils nächstgelegenen Knoten in q das Relaxationsprinzip an:
while(q ist nicht leer) {
u ← q.extractMin(); // entferne Knoten mit geringster Distanz
for(w in Adjazenz von u) {
d ← u.getDistanz() + gewicht[u.getIndex()][w.getIndex()];
if (w.getDistanz() > d) { // Dreiecksungleichung verletzt?
w.setDistanz(d); // setze Attribut distanz von w auf d
w.setVorgänger(u); // setze Attribut vorgänger von w auf u
q.decreaseKey(w,d); // sortiere Vorrangschlange mit neuer Distanz um
}
}
}
}Am Ende des Dijkstra-Algorithmus kann dann der günstigste Pfad für jeden Knoten aufgebaut werden, indem die vorherigen Kanten durchlaufen werden, bis man den Startknoten erreicht. Wenn es vom Startknoten aus keinen Pfad zu einem Knoten gibt, bleiben seine Kosten unendlich, was bedeutet, dass der Knoten niemals erreichbar ist.
Wie der Algorithmus von Dijkstra funktioniert, siehst Du erneut an einem einfachen Beispiel. Aber bis dahin wartet noch etwas Java-Code auf Dich.
Dijkstra Algorithmus Java
Wie implementiert man Dijkstra Algorithmus am besten in Java? Im Folgenden steht für Dich ein möglicher Quellcode Schritt für Schritt erklärt.
/* implementiert den single source shortest path Algorithmus nach Dijkstra
Es sind nur nicht-negative Kantenkosten zugelassen
Verwendet wird eine Priority-Queue der Knoten, gewichtet mit den Kosten
des vorläufig kürzesten Weges vom Startknoten bis zu diesem Knoten */
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class DijkstraAlgo{
// Dijkstra Algorithmus
public static void computePaths(Node source){
source.shortestDistance=0;
// Implemetierung einer Prioritätswarteschlange
PriorityQueue queue = new PriorityQueue();
queue.add(source);
while(!queue.isEmpty()){
Node u = queue.poll();
// Besuche die Nachbarknoten, beginnend mit dem nächsten Knoten (kleinste shortestDistance)
for(Edge e: u.adjacencies){
Node v = e.target;
double weight = e.weight;
// relaxen(u,v,weight)
double distanceFromU = u.shortestDistance+weight;
if(distanceFromU < v.shortestDistance){
// Entferne v aus der Warteschlange, um den Wert für die kürzeste Entfernung zu aktualisieren
queue.remove(v);
v.shortestDistance = distanceFromU;
v.parent = u;
queue.add(v);
}
}
}
}
public static List getShortestPathTo(Node target){
// verfolge Pfad vom Ziel zur Start
List path = new ArrayList();
for(Node node = target; node!=null; node = node.parent){
path.add(node);
}
// Kehre die Reihenfolge um, sodass sie von der Start zum Ziel erfolgt
Collections.reverse(path);
return path;
}
public static void main(String[] args){
// Initialisiere den Basisgraphen auf der deutschen Karte
Node n1 = new Node("München");
Node n2 = new Node("Köln");
Node n3 = new Node("Osnabrück");
Node n4 = new Node("Augsburg");
Node n5 = new Node("Frankfurt");
Node n6 = new Node("Hannover");
Node n7 = new Node("Paderborn");
Node n8 = new Node("Thüngen");
Node n9 = new Node("Leipzig");
Node n10 = new Node("Münster");
Node n11 = new Node("Dresden");
Node n12 = new Node("Nürnberg");
Node n13 = new Node("Rotterdam");
Node n14 = new Node("Hamburg");
// Kanten initialisieren
n1.adjacencies = new Edge[]{
new Edge(n2,75),
new Edge(n4,140),
new Edge(n8,118)
};
n2.adjacencies = new Edge[]{
new Edge(n1,75),
new Edge(n3,71)
};
n3.adjacencies = new Edge[]{
new Edge(n2,71),
new Edge(n4,151)
};
n4.adjacencies = new Edge[]{
new Edge(n1,140),
new Edge(n5,99),
new Edge(n3,151),
new Edge(n6,80),
};
n5.adjacencies = new Edge[]{
new Edge(n4,99),
new Edge(n13,211)
};
n6.adjacencies = new Edge[]{
new Edge(n4,80),
new Edge(n7,97),
new Edge(n12,146)
};
n7.adjacencies = new Edge[]{
new Edge(n6,97),
new Edge(n13,101),
new Edge(n12,138)
};
n8.adjacencies = new Edge[]{
new Edge(n1,118),
new Edge(n9,111)
};
n9.adjacencies = new Edge[]{
new Edge(n8,111),
new Edge(n10,70)
};
n10.adjacencies = new Edge[]{
new Edge(n9,70),
new Edge(n11,75)
};
n11.adjacencies = new Edge[]{
new Edge(n10,75),
new Edge(n12,120)
};
n12.adjacencies = new Edge[]{
new Edge(n11,120),
new Edge(n6,146),
new Edge(n7,138)
};
n13.adjacencies = new Edge[]{
new Edge(n7,101),
new Edge(n14,90),
new Edge(n5,211)
};
n14.adjacencies = new Edge[]{
new Edge(n13,90)
};
Node[] nodes = {n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14};
// Pfade berechnen
computePaths(n1);
// kürzeste Wege ausgeben
/*
for(Node n: nodes){
System.out.println("Distance to " + n + ": " + n.shortestDistance);
List path = getShortestPathTo(n);
System.out.println("Path: " + path);
} */
List path = getShortestPathTo(n13);
System.out.println("Path: " + path);
}
}
// Knoten definieren
class Node implements Comparable{
public final String value;
public Edge[] adjacencies;
public double shortestDistance = Double.POSITIVE_INFINITY;
public Node parent;
public Node(String val){
value = val;
}
public String toString(){
return value;
}
public int compareTo(Node other){
return Double.compare(shortestDistance, other.shortestDistance);
}
}
// Kanten definieren
class Edge{
public final Node target;
public final double weight;
public Edge(Node targetNode, double weightVal){
target = targetNode;
weight = weightVal;
}
}Output: Path : [München, Augsburg, Hannover, Paderborn, Rotterdam]
Um das Programm verständlicher zu machen, kann man es in mehrere Klassen unterteilen:
- Klasse Ausgabe(class main)
- Klasse Dijkstra (class DijkstraAlgo)
- Klasse Kanten(class Edge)
- Klasse Knoten(class Node).
Die Dijkstra-Klasse ist die wichtigste Klasse in Programm. Es wird verwendet, um die kürzeste Entfernung zwischen dem Abfahrtsknoten(München) und dem Zielknoten(Rotterdam) zu berechnen. In Dijkstra werden Knoten und Prioritätswarteschlangenverwaltungslisten zuerst initialisiert, dann wird der Dijkstra-Algorithmus ausgeführt: Bei jeder Iteration wird das Element u in der Warteschlange mit einem Abstand zum Startknoten gesucht, der am kleinsten ist.
Neben der kürzesten Pfadlänge berechnet Dijkstra auch die Programmausführungszeit, indem die Systemzeit zu Beginn und nach der Ausführung des Algorithmus gemessen wird.
Der Zweck der Ausgabeklasse besteht darin, die kürzeste Entfernung zwischen dem Start- (München) und dem Zielknoten (Rotterdam), die zuvor vom Dijkstra-Algorithmus berechnet wurde, auf der Konsole auszugeben.
Dijkstra Algorithmus Beispiel
Hands-On Time! Jetzt kannst Du endlich loslegen. Der Algorithmus soll nun anhand eines Beispiels erklärt werden: Im folgenden Graphen ist der kürzeste Weg vom Knoten links zu dem ganz rechts gesucht.
In der nachfolgenden Tabelle findest Du den ganzen Algorithmus-Durchlauf des Beispielgraphen.
Dijkstra Algorithmus – Durchlauf | Dijkstra Algorithmus – Durchlauf |
| |
| |
| |
| |
| |
| |
| |
| |
| |
Die Funktionsweise des Dijkstra-Algorithmus wird am verständlichsten durch ein konkretes Beispiel.
Der Routenplaner und Dijkstra-Algorithmus
Stell Dir vor, Dein Routenplaner soll den schnellsten Weg von einem Ort a zu einem anderen Ort d ermitteln.
Die Verbindungen benachbarter Orte sind unten in einem kantengewichteten Graphen dargestellt:
Die Gewichte geben in diesem Kontext die Fahrzeit zwischen den Orten an. Die Gewichte sind also positiv.
Ein möglicher Weg von a nach d ist a ⇢ b ⇢ c ⇢ d mit der Fahrzeit 1 + 3 + 8= 12. Findest du einen schnelleren Weg?
Lösung:
Oft wird eine tabellarische Form verwendet, um die Ergebnisse der einzelnen Iterationen des Dijkstra-Algorithmus zusammenzufassen. Dies wird für das obige Beispiel in der folgenden Tabelle dargestellt.
| Inhalt von P | entfernt | besuchte Kanten | Update-Operationen |
| (a, 0) | (a, 0) | (a, b),(a, e) | (b, 1),(e, 7) |
| (b, 1),(e, 7) | (b, 1) | (b, c) | (c, 4) |
| (c, 4),(e, 7) | (c, 4) | (c, d),(c, e),(c, f ) | (d, 12),(f , 10) |
| (e, 7),(f , 10),(d, 12) | (e, 7) | (e, f ) | (f , 8) |
| (f , 8),(d, 12) | (f , 8) | (f , c),(f , d) | (d, 10) |
| (d, 10) | (d, 10) | − | − |
Das folgende Diagramm zeigt den konstruierten aufspannenden Baum, die Besuchsfolge der Knoten und die berechneten Abstände.
Der schnellste Weg von a nach d ist also a ⇢ e ⇢ f ⇢ d (7+1+3=11) mit der Fahrzeit 11.
Dijkstra Algorithmus Laufzeit
Die Kosten des Dijkstra-Algorithmus werden durch die Operationen zum Entfernen von Knoten und zum Anpassen der Abstandswerte benachbarter Knoten bestimmt. Wenn alle Operationen in der Prioritätswarteschlange in O(1) durchgeführt werden können, dann sind die Kosten für einen Graphen mit m Kanten und n Knoten O(m + n). Für eine Prioritätswarteschlange, die auf einer verketteten Liste basiert, wird dies zu O(n2) übersetzt.
In der folgenden Tabelle findest Du eine Übersicht über die zeitliche Komplexität des Dijkstra-Algorithmus in Abhängigkeit von der verwendeten Datenstruktur. Übrigens hat Dijkstra selbst den Algorithmus mit einem Array implementiert.
| Datenstruktur | Tem | Ti | Tdk | Zeitkomplexitätallgemein | Zeitkomplexitätfür m ∈ O(n) |
| Array | O(n) | O(1) | O(1) | O(n² + m) | O(n²) |
| PriorityQueue | O(log n) | O(log n) | O(n) | O(n · log n + m · n) | O(n²) |
| TreeSet | O(log n) | O(log n) | O(log n) | O(n · log n + m · log n) | O(n · log n) |
| FibonacciHeap | O(log n) | O(1) | O(1) | O(n · log n + m) | O(n · log n) |
- Tem = TextractMinimum
- Ti = Tinsert
- Tdk = TdecreaseKey
Dijkstra Algorithmus Vorteile Nachteile
Was sind die größten Vorteile und Nachteile von Dijkstra Algorithmus? In der folgenden Tabelle findest Du die wichtigsten Vor- und Nachteile.
| Vorteile des Dijkstra Algorithmus | Nachteile des Dijkstra Algorithmus |
Seine lineare Zeitkomplexität macht es einfach, den Algorithmus für große Probleme zu verwenden. | Kann nicht mit negativen Gewichten umgehen. |
Der Algorithmus ist nützlich, um die kürzeste Entfernung zu finden, daher wird er auch in Google Maps und bei der Verkehrsberechnung verwendet. | Der größte Nachteil des Dijkstra-Verfahrens ist, dass der Graph nicht zielgerichtet durchsucht wird. |
Kann man Dijkstras Algorithmus verbessern oder alle oben genannten Nachteile lösen? Die Antwort ist ganz simpel: Ja!
Es gibt eine Weiterentwicklung des Dijkstra-Algorithmus, der die Prüfung auf falsche Pfade mittels Heuristik vorzeitig beendet und deterministisch immer den kürzesten Pfad findet: der A*-Algorithmus.
Bei einem negativ gewichteten Graphen würdest Du stattdessen einen anderen Greedy-Algorithmus, wie den Bellman-Ford-Algorithmus verwenden.
Der Bellman-Ford-Algorithmus, benannt nach seinen Entwicklern Richard Bellman und Lester Ford, wird verwendet, um die kürzesten Wege in Graphen zu finden. Negative Gewichtskanten können eingeschlossen werden, aber es muss darauf geachtet werden, negative Gewichtszyklen von der Berücksichtigung auszuschließen.
Dijkstras Algorithmus - Das Wichtigste
Nachweise
- Abb. 1 - "File:EdsgerDijkstra.jpg" by Hamilton Richards is licensed under CC BY-SA 3.0.
- algorithms.discrete.ma.tum.de: Der Dijkstra-Algorithmus. (13.10.2022)
- fh-swf.de:Algorithmik. (13.10.2022)
- literateprograms.org: Dijksra's Algorithm. (Java)
- happycoders.eu: Dijkstra-Algorithmus. (13.10.2022)
Schule 
Studium 
Ausbildung 
Karteikarten Erstelle und finde die besten Karteikarten.
Notizen Erstelle Notizen schneller als je zuvor.
Lernsets Alles was du brauchst an einem Ort.
Lernpläne Wöchentliche Ziele, Lern-Reminder, und mehr.
Spaced Repetition Nachhaltiger lernen.
AI powered learning Mithilfe unserer KI zum Lernerfolg
Blog 
