mini|Animation des Dijkstra-Algorithmus mini|Animation des Dijkstra-Algorithmus. Die roten Kanten bilden kürzeste Wege vom Startknoten. Die blaue Kante gibt an, für welchen Knoten der Abstand zum Startknoten geprüft wird. Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-AlgorithmenTobias Häberlein: Praktische Algorithmik mit Python. Oldenbourg, München 2012, ISBN 978-3-486-71390-9, S. 162 ff. und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er berechnet somit einen kürzesten Pfad zwischen dem gegebenen Startknoten und einem der (oder allen) übrigen Knoten in einem kantengewichteten Graphen (sofern dieser keine Negativkanten enthält).
Für unzusammenhängende ungerichtete Graphen ist der Abstand zu denjenigen Knoten unendlich, zu denen kein Pfad vom Startknoten aus existiert. Dasselbe gilt auch für gerichtete nicht stark zusammenhängende Graphen. Dabei wird der Abstand synonym auch als Entfernung, Kosten oder Gewicht bezeichnet.
Algorithmus Informelle Darstellung Die Grundidee des Algorithmus ist es, immer derjenigen Kante zu folgen, die den kürzesten Streckenabschnitt vom Startknoten aus verspricht. Andere Kanten werden erst dann verfolgt, wenn alle kürzeren Streckenabschnitte (auch über andere Knoten hinaus) beachtet wurden. Dieses Vorgehen gewährleistet, dass bei Erreichen eines Knotens kein kürzerer Pfad zu ihm existieren kann. Eine einmal berechnete Distanz zwischen dem Startknoten und einem besuchten Knoten wird gespeichert. Die aufsummierten Distanzen zu noch nicht abgearbeiteten Knoten können sich hingegen im Laufe des Algorithmus durchaus verändern, nämlich verringern. Dieses Vorgehen wird fortgesetzt, bis die Distanz des Zielknotens berechnet wurde () oder die Distanzen aller Knoten zum Startknoten bekannt sind ().
mini|hochkant=0.6|Berechnung der kürzesten Wege zum linken Knoten
Der Algorithmus lässt sich durch die folgenden Schritte beschreiben. Es werden sowohl die kürzesten (aufsummierten) Wegstrecken als auch deren Knotenfolgen berechnet.
Weise allen Knoten die beiden Eigenschaften (Attribute) „Distanz“ und „Vorgänger“ zu. Initialisiere die Distanz im Startknoten mit 0 und in allen anderen Knoten mit . Solange es noch unbesuchte Knoten gibt, wähle darunter denjenigen mit minimaler (aufsummierter) Distanz aus und Speichere, dass dieser Knoten schon besucht wurde. Berechne für alle noch unbesuchten Nachbarknoten die Gesamtdistanz des Pfades über die Summe des jeweiligen Kantengewichtes und der bereits berechneten Distanzen des Pfades vom Startknoten zum aktuellen Knoten. Ist dieser Wert für einen Knoten kleiner als die dort gespeicherte bisherige aufsummierte Distanz des Pfades, aktualisiere sie und setze den aktuellen Knoten als Vorgänger. Dieser Schritt wird auch als Update oder Relaxation/Relaxierung bezeichnet.
In dieser Form berechnet der Algorithmus ausgehend von einem Startknoten die kürzesten Wege zu allen anderen Knoten. Ist man dagegen nur an dem Weg zu einem ganz bestimmten Zielknoten interessiert, so kann man in Schritt (2) schon abbrechen, wenn der gesuchte Knoten der aktive ist.
mini|Negative Kantengewichte können zu nicht-optimalen Lösungen führen.
Aufgrund der Eigenschaft, einmal festgelegte Distanzen zum Startknoten nicht mehr zu verändern, gehört der Dijkstra-Algorithmus zu den Greedy-Algorithmen, die in jedem Schritt die momentan aussichtsreichste Teillösung bevorzugen. Anders als manche andere Greedy-Algorithmen berechnet der Dijkstra-Algorithmus jedoch stets eine optimale Lösung. Diese Eigenschaft basiert auf der Annahme, dass die kürzesten Teilstrecken zwischen Knoten in einem Pfad zusammen die kürzeste Strecke auf diesem Pfad bilden. Unter der Voraussetzung positiver Kantengewichte ist die Annahme gültig, denn fände man nachträglich einen kürzeren Weg vom Startknoten zu einem Zielknoten, hätte man auch dessen kürzere Teilstrecke früher untersuchen müssen, um den Algorithmus korrekt durchzuführen. Dann hätte man aber über die kürzere Teilstrecke den Zielknoten früher gefunden als auf dem längeren Weg.
Die Annahme trifft jedoch nicht mehr zu, wenn der Graph negative Kantengewichte enthält. Dann kann jede Teilstrecke für sich zwar eine kürzeste Strecke zwischen den Endpunkten sein, man könnte jedoch über einen längeren Teilweg die Gesamtdistanz verbessern, wenn eine negative Kante die Weglänge wieder reduziert. Im Bild mit den Knoten 1, 2, 3 und 4 würde der Dijkstra-Algorithmus den kürzesten Weg von 1 nach 3 über 2 finden, da der Schritt zu 4 insgesamt schon länger ist als der gesamte obere Pfad. Die negative Kante bewirkt aber, dass der untere Pfad kürzer ist.
Algorithmus in Pseudocode Die folgenden Zeilen Pseudocode beschreiben eine Funktion namens Dijkstra, die einen Graphen und einen Startknoten im Graphen als Eingabe erhält. Der Startknoten gibt den Knoten an, von dem aus die kürzesten Wege zu allen Knoten gesucht werden. Das Ergebnis ist eine Liste, die zu jedem Knoten den Vorgängerknoten auf dem Weg vom Startknoten zu angibt.
Der Graph besteht aus Knoten und gewichteten Kanten, wobei das Gewicht die Entfernung zwischen den Knoten darstellt. Existiert eine Kante zwischen zwei Knoten, so sind die Knoten jeweils Nachbarn. Der aktuell im Teilschritt betrachtete Knoten wird mit bezeichnet und wird „Betrachtungsknoten“ genannt. Die möglichen, kommenden Nachbarknoten werden in der jeweiligen, kommenden Zwischenuntersuchung mit jeweils als „Prüfknoten“ bezeichnet. Das Kantengewicht zwischen Betrachtungsknoten und jeweiligen Prüfknoten wird im Pseudocode als abstand_zwischen(u,v) angegeben.
Der Zahlenwert von abstand[v] enthält in dem Untersuchungszweig die jeweilige Gesamtentfernung, die die Teilentfernungen vom Startpunkt über mögliche Zwischenknoten und den aktuellen Knoten bis zum nächsten zu untersuchenden Knoten summiert.
Zunächst werden abhängig vom Graphen und Startknoten die Abstände und Vorgänger initialisiert. Dies geschieht in der Methode initialisiere. Der eigentliche Algorithmus verwendet eine Methode distanz_update, die ein Update der Abstände durchführt, falls ein kürzerer Weg gefunden wurde.
1 Funktion Dijkstra(Graph, Startknoten): 2 initialisiere(Graph,Startknoten,abstand[],vorgänger[],Q) 3 solange Q nicht leer: // Der eigentliche Algorithmus 4 u := Knoten in Q mit kleinstem Wert in abstand[] 5 entferne u aus Q // für u ist der kürzeste Weg nun bestimmt 6 für jeden Nachbarn v von u: 7 falls v in Q: // falls noch nicht berechnet 8 distanz_update(u,v,abstand[],vorgänger[]) // prüfe Abstand vom Startknoten zu v 9 return vorgänger[]
Die Initialisierung setzt die Abstände auf unendlich und die Vorgänger als unbekannt. Nur der Startknoten hat die Distanz 0. Die Menge enthält die Knoten, zu denen noch kein kürzester Weg gefunden wurde.
1 Methode initialisiere(Graph,Startknoten,abstand[],vorgänger[],Q): 2 für jeden Knoten v in Graph: 3 abstand[v] := unendlich 4 vorgänger[v] := null 5 abstand[Startknoten] := 0 6 Q := Alle Knoten in Graph
Der Abstand vom Startknoten zum Knoten verkürzt sich dann, wenn der Weg zu über kürzer als der bisher bekannte Weg ist. Entsprechend wird zum Vorgänger von auf dem kürzesten Weg.
1 Methode distanz_update(u,v,abstand[],vorgänger[]): 2 alternativ := abstand[u] + abstand_zwischen(u, v) // Weglänge vom Startknoten nach v über u 3 falls alternativ < abstand[v]: 4 abstand[v] := alternativ 5 vorgänger[v] := u
Falls man nur am kürzesten Weg zwischen zwei Knoten interessiert ist, kann man den Algorithmus nach Zeile 5 der Dijkstra-Funktion abbrechen lassen, falls = Zielknoten ist.
Den kürzesten Weg zu einem Zielknoten kann man nun durch Iteration über die vorgänger ermitteln:
1 Funktion erstelleKürzestenPfad(Zielknoten,vorgänger[]) 2 Weg[] := [Zielknoten] 3 u := Zielknoten 4 solange vorgänger[u] nicht null: // Der Vorgänger des Startknotens ist null 5 u := vorgänger[u] 6 füge u am Anfang von Weg[] ein 7 return Weg[]
Implementierung Knoten und Kanten zwischen Knoten lassen sich meistens durch Matrizen oder Zeigerstrukturen darstellen. Auch auf den Vorgänger eines Knotens kann ein Zeiger verweisen. Die Abstände der Knoten können in Feldern gespeichert werden.
Für eine effiziente Implementierung wird die Menge Q der Knoten, für die noch kein kürzester Weg gefunden wurde, durch eine Prioritätswarteschlange implementiert. Die aufwändige Initialisierung findet nur einmal statt, dafür sind die wiederholten Zugriffe auf Q effizienter. Als Schlüsselwert für den Knoten wird sein jeweiliger Abstand verwendet, der im Pseudocode mit abstand[v] angegeben ist. Verkürzt sich der Abstand, ist eine teilweise Neusortierung der Warteschlange nötig.
Als Datenstruktur bietet sich hierfür eine Entfernungstabelle oder eine Adjazenzmatrix an.
Programmierung Das folgende Beispiel in der Programmiersprache C++ zeigt die Implementierung des Dijkstra-Algorithmus für einen ungerichteten Graphen, der als Adjazenzliste gespeichert wird. Bei der Ausführung des Programms wird die Funktion main verwendet, die einen kürzesten Weg auf der Konsole ausgibt.Rosetta Code: Dijkstra's algorithmGeeksforGeeks: Dijkstra’s shortest path algorithm Code-Schnipsel #include <iostream> #include <limits> #include <vector> #include <list> #include <set> #include <map> #include <algorithm> #include <iterator> #include <string> using namespace std;
const double maximumWeight = numeric_limits<double>::infinity(); // Konstante für das maximale Gewicht
// Datentyp, der die Nachbarknoten eines Knotens definiert struct neighbor { int targetIndex; // Index des Zielknotens string name; // Name des double weight; // Gewicht der Kante neighbor(int _target, string _name, double _weight) : targetIndex(_target), name(_name), weight(_weight) { }
// Berechnet die kürzesten Wege für den Knoten mit startIndex. Der gerichtete Graph wird als Adjazenzliste übergeben. auto ComputeShortestPathsByDijkstra(int startIndex, const vector<vector<neighbor>>& adjacencyList) { struct result { vector<double> minimumDistances; vector<int> previousVertices; map<int, string> vertexNames;
auto numberOfVertices = adjacencyList.size(); auto minimumDistances = vector(numberOfVertices, maximumWeight); auto previousVertices = vector(numberOfVertices, -1); auto vertexNames = map{make_pair(startIndex, ""s)}; auto vertexQueue = set{make_pair(0.0, startIndex)}; minimumDistances[startIndex] = 0;
while (!vertexQueue.empty()) // Solange die Warteschlange nicht leer ist
auto distance = vertexQueue.begin()->first; // Abstand auto index = vertexQueue.begin()->second; vertexQueue.erase(vertexQueue.begin()); // Entfernt den ersten Knoten der Warteschlange const vector<neighbor>& neighbors {adjacencyList[index]}; // Diese for-Schleife durchläuft alle Nachbarn des Knoten mit index for(const auto& neighborIterator : neighbors)
auto targetIndex = neighborIterator.targetIndex; // Index des Nachbarknotens auto name = neighborIterator.name; // Name des Nachbarknotens auto weight = neighborIterator.weight; // Abstand zum Nachbarknoten auto currentDistance = distance + weight; // Abstand vom Startknoten zum Knoten mit index if (currentDistance < minimumDistances[targetIndex]) // Wenn der Abstand zum Nachbarknoten kleiner als die Länge des bisher kürzesten Wegs ist
vertexQueue.erase(make_pair(minimumDistances[targetIndex], targetIndex)); // Entfernt den Knoten aus der Warteschlange vertexNames.erase(targetIndex); // Entfernt den Namen des Knotens aus der Zuordnungstabelle minimumDistances[targetIndex] = currentDistance; // Speichert den Abstand vom Startknoten previousVertices[targetIndex] = index; // Speichert den Index des Vorgängerknotens vertexQueue.insert(make_pair(minimumDistances[targetIndex], targetIndex)); // Fügt den Knoten der Warteschlange hinzu vertexNames.insert(make_pair(targetIndex, name)); // Fügt den Namen des Knotens der Zuordnungstabelle hinzu