imported>Krdbot: Bot: Entferne 2 weiche Trennzeichen

2025-08-25T17:56:27Z

Neue Seite

[[Datei:Dijkstra Animation.gif|mini|[[Animation]] des Dijkstra-Algorithmus]]
[[Datei:DijkstraDemo.gif|mini|[[Animation]] des Dijkstra-Algorithmus. Die roten [[Kante (Graphentheorie)|Kanten]] bilden [[Kürzester Weg|kürzeste Wege]] vom Startknoten. Die blaue Kante gibt an, für welchen [[Knoten (Graphentheorie)|Knoten]] der [[Abstand (Graphentheorie)|Abstand]] zum Startknoten geprüft wird.]]
Der '''Algorithmus von Dijkstra''' (nach seinem Erfinder [[Edsger W. Dijkstra]]) ist ein [[Algorithmus]] aus der Klasse der [[Greedy-Algorithmus|Greedy-Algorithmen]]<ref>Tobias Häberlein: ''Praktische Algorithmik mit Python.'' Oldenbourg, München 2012, ISBN 978-3-486-71390-9, S. 162 ff.</ref> und löst das Problem der [[Kürzester Pfad|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 [[Kantengewichteter Graph|kantengewichteten Graphen]] (sofern dieser keine Negativkanten enthält).

Für [[Zusammenhang von Graphen|unzusammenhängende]] [[Ungerichtete Kante|ungerichtete]] Graphen ist der Abstand zu denjenigen Knoten unendlich, zu denen kein Pfad vom Startknoten aus existiert. Dasselbe gilt auch für [[Gerichtete Kante|gerichtete]] nicht [[Stark zusammenhängender Graph|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 (Graphentheorie)|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 [[Knoten (Graphentheorie)|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 (''{{lang|en|single-pair shortest path}}'') oder die Distanzen aller Knoten zum Startknoten bekannt sind (''{{lang|en|single-source shortest path}}'').

[[Datei:Dijkstra's algorithm.svg|mini|hochkant=0.6|Berechnung der [[Kürzester Weg|kürzesten Wege]] zum linken [[Knoten (Graphentheorie)|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 <math>\infty</math>.
# 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 Distanz 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.

[[Datei:Dijkstra-negative-edge-weights-error.svg|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 <math>v</math> den Vorgängerknoten auf dem Weg vom Startknoten zu <math>v</math> 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 <math>u</math> bezeichnet und wird „Betrachtungsknoten“ genannt. Die möglichen, kommenden Nachbarknoten werden in der jeweiligen, kommenden Zwischenuntersuchung mit jeweils <math>v</math> als „Prüfknoten“ bezeichnet. Das Kantengewicht zwischen Betrachtungsknoten <math>u</math> und jeweiligen Prüfknoten <math>v</math> 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 <math>u</math> bis zum nächsten zu untersuchenden Knoten <math>v</math> 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.

<syntaxhighlight lang="text">
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[]
</syntaxhighlight>

Die Initialisierung setzt die Abstände auf unendlich und die Vorgänger als unbekannt. Nur der Startknoten hat die Distanz 0. Die Menge <math>Q</math> enthält die Knoten, zu denen noch kein kürzester Weg gefunden wurde.

<syntaxhighlight lang="text">
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
</syntaxhighlight>

Der Abstand vom Startknoten zum Knoten <math>v</math> verkürzt sich dann, wenn der Weg zu <math>v</math> über <math>u</math> kürzer als der bisher bekannte Weg ist. Entsprechend wird <math>u</math> zum Vorgänger von <math>v</math> auf dem kürzesten Weg.

<syntaxhighlight lang="text">
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
</syntaxhighlight>

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 <math>u</math> = ''Zielknoten'' ist.

Den kürzesten Weg zu einem ''Zielknoten'' kann man nun durch Iteration über die ''vorgänger'' ermitteln:

<syntaxhighlight lang="text">
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[]
</syntaxhighlight>

=== Implementierung ===
Knoten und Kanten zwischen Knoten lassen sich meistens durch [[Matrix (Mathematik)|Matrizen]] oder [[Zeiger (Informatik)|Zeigerstrukturen]] darstellen. Auch auf den Vorgänger eines Knotens kann ein Zeiger verweisen. Die Abstände der Knoten können in [[Feld (Datentyp)|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 [[Vorrangwarteschlange|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 [[Ungerichteter Graph|ungerichteten Graphen]], der als [[Adjazenzliste]] gespeichert wird. Bei der Ausführung des Programms wird die [[Funktion (Informatik)|Funktion]] ''main'' verwendet, die einen [[Kürzester Weg|kürzesten Weg]] auf der Konsole ausgibt.<ref>Rosetta Code: [https://rosettacode.org/wiki/Dijkstra%27s_algorithm Dijkstra's algorithm]</ref><ref>GeeksforGeeks: [https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/ Dijkstra’s shortest path algorithm]</ref>
{| class="wikitable left mw-collapsible mw-collapsed font-size: 105.3%;"
|style="text-align:left; font-size: 95%;"| '''Code-Schnipsel'''  
|-
|
<syntaxhighlight lang="c++">
#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
}
}
}
return result{minimumDistances, previousVertices, vertexNames};
}

// Gibt einen kürzesten Weg für den Knoten mit index zurück
auto GetShortestPathTo(int index, const vector<int>& previousVertices, const map<int, string>& vertexNames)
{
list<string> path;
for (; index != -1; index = previousVertices[index]) // Diese for-Schleife durchläuft den Weg
{
path.push_front(vertexNames.at(index)); // Fügt den Namen des Vorgängerknotens hinzu
}
return path;
}

// Hauptfunktion die das Programm ausführt
int main()
{
// Initialisiert die Adjazenzliste des gerichteten Graphen mit 6 Knoten
vector<vector<neighbor>> adjacencyList(6);

adjacencyList[0].push_back(neighbor(1, "Knoten 1", 7));
adjacencyList[0].push_back(neighbor(2, "Knoten 2", 9));
adjacencyList[0].push_back(neighbor(5, "Knoten 5", 14));

adjacencyList[1].push_back(neighbor(0, "Knoten 0", 7));
adjacencyList[1].push_back(neighbor(2, "Knoten 2", 10));
adjacencyList[1].push_back(neighbor(3, "Knoten 3", 15));

adjacencyList[2].push_back(neighbor(0, "Knoten 0", 9));
adjacencyList[2].push_back(neighbor(1, "Knoten 1", 10));
adjacencyList[2].push_back(neighbor(3, "Knoten 3", 11));
adjacencyList[2].push_back(neighbor(5, "Knoten 5", 2));

adjacencyList[3].push_back(neighbor(1, "Knoten 1", 15));
adjacencyList[3].push_back(neighbor(2, "Knoten 2", 11));
adjacencyList[3].push_back(neighbor(4, "Knoten 4", 6));

adjacencyList[4].push_back(neighbor(3, "Knoten 3", 6));
adjacencyList[4].push_back(neighbor(5, "Knoten 5", 9));

adjacencyList[5].push_back(neighbor(0, "Knoten 0", 14));
adjacencyList[5].push_back(neighbor(2, "Knoten 2", 2));
adjacencyList[5].push_back(neighbor(4, "Knoten 4", 9));

auto [minimumDistances, previousVertices, vertexNames] = ComputeShortestPathsByDijkstra(0, adjacencyList); // Aufruf der Methode, die die kürzesten Wege für den Knoten 0 zurückgibt
cout << "Abstand von Knoten 0 nach Knoten 4: " << minimumDistances[4] << endl; // Ausgabe auf der Konsole
auto path = GetShortestPathTo(4, previousVertices, vertexNames); // Aufruf der Methode, die einen kürzesten Weg von Knoten 0 nach Knoten 4 zurückgibt
cout << "Kürzester Weg:"; // Ausgabe auf der Konsole
copy(path.begin(), path.end(), ostream_iterator<string>(cout, " ")); // Ausgabe auf der Konsole
cout << endl; // Ausgabe auf der Konsole
}
</syntaxhighlight>
|}

== Beispiel mit bekanntem Zielknoten ==
Ein Beispiel für die Anwendung des Algorithmus von Dijkstra ist die Suche nach einem kürzesten Pfad auf einer Landkarte.<ref>[http://www.vice.com/en/article/4x3pp9/the-simple-elegant-algorithm-that-makes-google-maps-possible ''The Simple, Elegant Algorithm That Makes Google Maps Possible.''] Bei: ''[[Vice (Magazin)|VICE.]]'' Abgerufen am 3. Oktober 2020.</ref> Im hier verwendeten Beispiel will man in der unten gezeigten Landkarte von [[Deutschland]] einen kürzesten Pfad von [[Frankfurt am Main|Frankfurt]] nach [[München]] finden.

Die Zahlen auf den Verbindungen zwischen zwei Städten geben jeweils die Entfernung zwischen den beiden durch die Kante verbundenen Städten an. Die Zahlen hinter den Städtenamen geben die ermittelte Distanz der Stadt zum Startknoten ''Frankfurt'' an, ∞ steht dabei für eine unbekannte Distanz. Die hellgrau unterlegten Knoten sind die Knoten, deren Abstand relaxiert wird (also verkürzt wird, falls eine kürzere Strecke gefunden wurde), die dunkelgrau unterlegten Knoten sind diejenigen, zu denen der kürzeste Weg von Frankfurt bereits bekannt ist.

Die Auswahl des nächsten Nachbarn erfolgt nach dem Prinzip einer Prioritätswarteschlange. Relaxierte Abstände erfordern daher eine Neusortierung.

<div style="clear:both;"></div>
<gallery widths="300" heights="250" perrow="2" caption="Beispiel">
MapGermanyGraph.svg|Ausgangssituation: Nicht-initialisierter Graph mit Startknoten Frankfurt und Zielknoten München
DijkstraStep01.svg|Entfernungen vom Startknoten (Frankfurt) ermitteln (''Relaxierung''), Neusortieren der Prioritätswarteschlange Q (1. Mannheim, 2. Kassel, 3. Würzburg, …)
DijkstraStep02.svg|Mannheim ist der nächstliegende Knoten, Relaxierung mit dem Nachbarknoten Karlsruhe, nächster Vorgänger von Karlsruhe ist nun Mannheim, Neusortieren von Q (1. Karlsruhe, 2. Kassel, 3. Würzburg, …)
DijkstraStep03.svg|Dem Startpunkt nächstliegender zu untersuchender Knoten laut Q ist nun Karlsruhe, Relaxierung mit Augsburg, Neusortieren von Q (1. Kassel, 2. Würzburg, 3. Augsburg, …)
DijkstraStep04.svg|Nächstliegender zu untersuchender Knoten ist nun Kassel, Relaxierung mit München, Neusortieren von Q (1. Würzburg, 2. Augsburg, 3. München, …)
DijkstraStep05.svg|Nächstliegender zu untersuchender Knoten ist nun Würzburg, Relaxierung mit Erfurt und Nürnberg, Neusortieren von Q (1. Nürnberg, 2. Erfurt, 3. Augsburg, 4. München, …)
DijkstraStep06.svg|Nächstliegender zu untersuchender Knoten ist nun Nürnberg, Relaxierung mit München und Stuttgart, Neusortieren von Q (1. Erfurt, 2. Augsburg, 3. München, 4. Stuttgart, …)
DijkstraStep07.svg|Nächstliegender zu untersuchender Knoten ist nun Erfurt, Relaxierung mit niemandem, Neusortieren von Q (1. Augsburg, 2. München, 3. Stuttgart, …)
DijkstraStep08.svg|Nächstliegender zu untersuchender Knoten ist nun Augsburg, Relaxierung mit München, Neusortieren von Q (1. München, 2. Stuttgart …)
DijkstraStep09.svg|Zielknoten soll untersucht werden: Kürzester Weg nach München ist nun bekannt; Rekonstruktion mittels ''erstelleKürzestenPfad()''. Dieser ist: Frankfurt-Würzburg-Nürnberg-München.
</gallery>

== Grundlegende Konzepte und Verwandtschaften ==
Ein alternativer Algorithmus zur Suche kürzester Pfade, der sich dagegen auf das [[Optimalitätsprinzip von Bellman]] stützt, ist der [[Floyd-Warshall-Algorithmus]]. Das Optimalitätsprinzip besagt, dass, wenn der kürzeste Pfad von A nach C über B führt, der Teilpfad A B auch der kürzeste Pfad von A nach B sein muss.

Ein weiterer alternativer Algorithmus ist der [[A*-Algorithmus]], der den Algorithmus von Dijkstra um eine Abschätzfunktion erweitert. Falls diese gewisse Eigenschaften erfüllt, kann damit der kürzeste Pfad unter Umständen schneller gefunden werden.

Es gibt verschiedene Beschleunigungstechniken für den Dijkstra-Algorithmus, zum Beispiel [[Arcflag]].

== Berechnung eines Spannbaumes ==
[[Datei:Dijkstra-MSG-Negativbsp.svg|gerahmt|Ein [[Graph (Graphentheorie)|Graph]], bei dem der durch den Dijkstra-Algorithmus (startend in s) berechnete [[Spannbaum]] kein minimaler Spannbaum des Graphen ist.]]

Nach Ende des Algorithmus ist in den Vorgängerzeigern ''π'' ein Teil-[[Spannbaum]] der [[Zusammenhang von Graphen|Komponente]] von <math>s</math> aus kürzesten Pfaden von <math>s</math> zu allen Knoten der Komponente, die in die Queue aufgenommen wurden, verzeichnet. Dieser Baum ist jedoch nicht notwendigerweise auch minimal, wie die Abbildung zeigt:

Sei <math>x</math> eine Zahl größer 0. Minimal spannende Bäume sind entweder durch die Kanten <math>\left\{ a,s \right\}</math> und <math>\left\{ a,b \right\}</math> oder <math>\left\{ b,s \right\}</math> und <math>\left\{ a,b \right\}</math> gegeben. Die Gesamtkosten eines minimal spannenden Baumes betragen <math>2+x</math>. Dijkstras Algorithmus liefert mit Startpunkt <math>s</math> die Kanten <math>\left\{ a,s \right\}</math> und <math>\left\{ b,s \right\}</math> als Ergebnis. Die Gesamtkosten dieses spannenden Baumes betragen <math>2+2x</math>.

Die Berechnung eines [[Spannbaum|minimalen Spannbaumes]] ist mit dem [[Algorithmus von Prim]] oder dem [[Algorithmus von Kruskal]] möglich.

== Zeitkomplexität ==
Die folgende Abschätzung gilt nur für Graphen, die keine negativen Kantengewichte enthalten.

Die Laufzeit des Dijkstra-Algorithmus hängt ab von der Anzahl der Kanten <math>|E|</math> und der Anzahl der Knoten <math>|V|</math>. Die genaue Zeitkomplexität hängt von der Datenstruktur <math>Q</math> ab, in der die Knoten gespeichert werden.
Für alle Implementierungen von <math>Q</math> gilt:
:<math>O(|E| \cdot T_\mathrm{dk} + |V| \cdot T_\mathrm{em})</math>
wobei <math>T_\mathrm{dk}</math> und <math>T_\mathrm{em}</math> für die Komplexität der ''decrease-key''- und ''extract-minimum''-Operationen bei <math>Q</math> stehen. Die einfachste Implementierung für <math>Q</math> ist eine Liste oder ein Array. Dabei ist die Zeitkomplexität <math>O(|E| + |V|^2) = O(|V|^2)</math>.

Im Normalfall wird man hier auf eine [[Vorrangwarteschlange]] zurückgreifen, indem man dort die Knoten als Elemente mit ihrer jeweiligen bisherigen Distanz als Schlüssel/Priorität verwendet.

Die optimale Laufzeit für einen Graphen <math>G = (V, E)</math> beträgt <math>O(|V| \log(|V|) + |E|)</math> mittels Verwendung eines [[Fibonacci-Heap|Fibonacci-Heaps]] für den Dijkstra-Algorithmus.<ref>{{Literatur |Autor=Thomas H. Cormen |Titel=Introduction to Algorithms |Verlag=MIT Press |Datum= |Seiten=663}}</ref>

== Brechen der „Sortierbarriere“ ==
Forschung aus dem Jahr 2025 zeigt, dass die Schranke <math>O(m+n\log n)</math> nicht grundsätzlich optimal für SSSP in reell gewichteten Graphen ist, sofern nur Distanzen, nicht aber die vollständige Reihenfolge der Knoten nach Distanz ausgegeben werden muss. Duan u. a. (2025) geben einen deterministischen Algorithmus mit Laufzeit <math>O(m \log^{2/3} n)</math> im Comparison-Addition-Modell (nur Vergleiche und Additionen der Kantengewichte, konstante Kosten pro Operation) für gerichtete Graphen mit nichtnegativen Gewichten an.<ref name="Duan2025">{{Internetquelle |url=https://arxiv.org/abs/2504.17033v2 |titel=Breaking the Sorting Barrier for Directed Single-Source Shortest Paths |autor=Ran Duan; Jiayi Mao; Xiao Mao; Xinkai Shu; Longhui Yin |werk=arXiv |datum=31. Juli 2025 |zugriff=13. August 2025}}</ref>

Der Ansatz verringert die Größe der „Frontier“ (Menge der relevanten Kandidatenknoten) rekursiv, kombiniert Dijkstra-artige Extraktionen mit Bellman-Ford-artigen Mehrschritt-Relaxationen und nutzt partielle Priorisierung statt vollständiger Sortierung. Dadurch wird die klassische Sortierbarriere umgangen. Das Ergebnis belegt, dass Dijkstras Algorithmus für die reine Distanzberechnung auf dünn besetzten (''sparse'') Graphen nicht optimal ist; eine universelle Optimalität bleibt bestehen, wenn die Ausgabe die vollständige Distanzordnung verlangt (siehe u. a. Haeupler, Hladík, Rozhoň, Tarjan, Tětek, 2024).<ref name="Duan2025" />

Zur Einordnung: Für ungerichtete Graphen existieren bereits frühere deterministische Verbesserungen im selben Modell, z. B. durch Pettie und Ramachandran (2005) mit einer Laufzeit von <math>O(m \alpha(m,n) + \min\{n\log n,\, n\log\log r\})</math>, wobei <math>\alpha</math> die inverse Ackermann-Funktion und <math>r</math> das Verhältnis zweier Kantengewichte bezeichnet; die Arbeit von Duan u. a. durchbricht die Sortierbarriere explizit für den gerichteten Fall.<ref name="Duan2025" />

== Anwendungen ==
[[Routenplaner]] sind ein prominentes Beispiel, bei dem dieser Algorithmus eingesetzt werden kann. Der Graph repräsentiert hier das Verkehrswegenetz, das verschiedene Punkte miteinander verbindet. Gesucht ist die kürzeste Route zwischen zwei Punkten.

Einige [[Topologischer Deskriptor|topologische Indizes]], etwa der [[Balaban-J-Index|J-Index]] von Balaban, benötigen gewichtete Distanzen zwischen den Atomen eines [[Molekül]]s. Die Gewichtung ist in diesen Fällen die Bindungsordnung.

Dijkstras Algorithmus wird auch im [[Internet]] als [[Routing]]-Algorithmus im [[Open Shortest Path First|OSPF]]-, [[IS-IS]]- und [[Optimized Link State Routing|OLSR]]-Protokoll eingesetzt. Das letztere ''Optimized Link State Routing''-Protokoll ist eine an die Anforderungen eines mobilen drahtlosen LANs angepasste Version des [[Link-State|Link State Routing]]. Es ist wichtig für mobile [[Ad-hoc-Netz]]e. Eine mögliche Anwendung davon sind die [[Freies Funknetz|freien Funknetze]].

Auch bei der Lösung des [[Münzproblem]]s, eines zahlentheoretischen Problems, das auf den ersten Blick nichts mit Graphen zu tun hat, kann der Dijkstra-Algorithmus eingesetzt werden.

== Andere Verfahren zur Berechnung kürzester Pfade ==
Hat man genug Informationen über die Kantengewichte im Graphen, um daraus eine [[Heuristik]] für die Kosten einzelner Knoten ableiten zu können, ist es möglich, den Algorithmus von Dijkstra zum [[A*-Algorithmus]] zu erweitern. Um alle kürzesten Pfade von einem Knoten zu allen anderen Knoten in einem Graphen zu berechnen, kann man auch den [[Bellman-Ford-Algorithmus]] verwenden, der mit negativen Kantengewichten umgehen kann. Der [[Algorithmus von Floyd und Warshall]] berechnet schließlich die kürzesten Pfade aller Knoten zueinander.

== Literatur ==
* {{BibISBN|3486275151|Seite=598–604}}
* [[Robert Sedgewick (Informatiker)|Robert Sedgewick]]: ''Algorithms in C++ Part 5: Graph Algorithms.'' Indianapolis 2002, ISBN 0-201-36118-3, S. 293–302.
* [[Edsger W. Dijkstra]]: ''A note on two problems in connexion with graphs.'' In: ''Numerische Mathematik.'' 1, 1959, S. 269–271; [http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf ma.tum.de] (PDF; 739 kB).

== Weblinks ==
{{commons|Dijkstra's algorithm|Algorithmus von Dijkstra}}
{{Wikibooks|Algorithmensammlung: Graphentheorie: Dijkstra-Algorithmus|Dijkstra-Algorithmus|suffix=Implementierungen in der Algorithmensammlung}}
* [http://web.archive.org/web/20210917222324/https://www.gilles-bertrand.com/2014/03/dijkstra-algorithm-python-example-source-code-shortest-path.html Python-Implementierung mit Erklärungen]
* [https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html Implementierung] in der freien [[Python (Programmiersprache)|Python]]-[[Programmbibliothek|Bibliothek]] [[NetworkX]]
* [https://algorithms.discrete.ma.tum.de/graph-algorithms/spp-dijkstra/index_de.html Interaktives Applet zur Lernen, Ausprobieren und Demonstrieren des Algorithmus]
* [http://www.uweschmidt.org/dijkstravis Interaktive Visualisierung und Animation von Dijkstras Algorithmus, geeignet für Personen ohne Vorkenntnisse von Algorithmen] (englisch)
* [http://computer.howstuffworks.com/routing-algorithm3.htm Implementierung in C] (englisch)
* [http://algo2.iti.uni-karlsruhe.de/singler/algorithmus-der-woche/Kuerzeste%20Wege.pdf Erklärung anhand eines analogen Modells] (PDF; 213 kB)
* [http://jgrapht.org/ Öffentliche Softwarebibliothek in Java mit diesem und anderen Algorithmen] (englisch)
* [http://sourceforge.net/projects/dijkstromania/ Java Implementierung – Simulation / Auswertung] (englisch)
* {{Webarchiv |url=http://www.hann3mann.de/artikel/dijkstra-algorithmus-in-c-csharp/ |text=''Dijkstra Algorithmus in C# (csharp).'' |archive-is=20130211062327}}.

== Einzelnachweise ==
<references />

[[Kategorie:Optimierungsalgorithmus|Dijkstra, Algorithmus von]]
[[Kategorie:Graphsuchalgorithmus]]
[[Kategorie:Routing]]
[[Kategorie:Reise- und Routenplanung]]

Dijkstra-Algorithmus - Versionsgeschichte

imported>Krdbot: Bot: Entferne 2 weiche Trennzeichen