Quelltext der Seite Dijkstra-Algorithmus

{{Thumbnailbox|
INHALT={{#mermaid:graph LR
a((A))
b((B))
c((C))
d((D))
e((E))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
}}
|CAPTION=Ein Beispielgraph}}Der [[Dijkstra-Algorithmus]] ist ein [[Algorithmus]] zum Finden kürzester Wege in einem gewichteten [[Graph|Graphen]]. Konkret findet dieser Algorithmus von einem gegebenen Startknoten aus die kürzesten Wege zu allen anderen Knoten im Graphen.

Er wurde 1956 von Edsger Dijkstra entdeckt und funktioniert nur bei Graphen mit ausschließlich positiven Kantenlängen. Die Idee dahinter ist nämlich Folgende:

Wir betrachten zunächst alle Nachbarn des Startknoten. Derjenige von ihnen mit der kürzesten Entfernung zum Startknoten ''kann'' auch über Umwege nicht schneller erreicht werden, da der Weg zu all seinen Nachbarn schon länger ist und dies auch durch eine negative Kante nicht ausgeglichen werden kann. Diesen Knoten können wir also als gesetzt betrachten und auch all seine Nachbarn hinzuziehen. Wieder gilt: derjenige Knoten mit der kürzesten Entfernung zum Startknoten ''kann'' nicht schneller erreicht werden... und so weiter, bis alle Entfernungen berechnet sind.

# Markiere alle Knoten des Graphen als ''noch nicht besucht''.
# Weise jedem Knoten des Graphen seine Entfernung vom Startknoten zu. Für den Startknoten ist diese offensichtlich 0, für alle anderen Knoten wird sie vorerst auf <math>\infty</math> gesetzt.
# Solange es noch unbesuchte Knoten mit einer Entfernung <math>< \infty</math> gibt, führe folgende Schritte aus:
## Wähle einen unbesuchten Knoten  <math>v</math> mit der kürzesten Entfernung zum Startknoten aus.
## Markiere <math>v</math> als ''besucht''.
## Betrachte nun alle Nachbarknoten <math>u</math> von <math>v</math>:
### Wenn die Entfernung von <math>u</math> zum Startknoten größer ist als die Entfernung vom Startknoten zu <math>v</math> plus die Länge der Kante zwischen <math>u</math> und <math>v</math>, dann setze die Entfernung von <math>u</math> zum Startknoten auf die Entfernung vom Startknoten zu <math>v</math> plus die Länge der Kante zwischen <math>u</math> und <math>v</math>

== Beispiel ==

In diesem Beispiel suchen wir die kürzesten Wege vom Knoten B aus.

{{Hinweisbaustein|style=border: none; padding: none
|INHALT=
{{Thumbnailbox|
INHALT={{#mermaid:graph LR
a(("A (∞)"))
b(("B (0)"))
c(("C (∞)"))
d(("D (∞)"))
e(("E (∞)"))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
}}
|CAPTION=Vorbereitung: Startknoten B erhält Entfernung 0,<br>alle anderen Knoten erhalten Entfernung <math>\infty</math>.
|ALIGN=left
|CLASS=noclear}}

{{Thumbnailbox|
INHALT={{#mermaid:graph LR
a(("A (3)"))
b(("B (0)"))
c(("C (7)"))
d(("D (5)"))
e(("E (1)"))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
style b fill:#00B169;
}}
|CAPTION=Schritt 1: markiere B als besucht und berechne für alle seine Nachbarn die Entfernung zu B.
|ALIGN=left
|CLASS=noclear}}

{{Thumbnailbox|
INHALT={{#mermaid:graph LR
a(("A (3)"))
b(("B (0)"))
c(("C (7)"))
d(("D (5)"))
e(("E (1)"))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
style b fill:#00B169;
style e fill:#00B169;
linkStyle 4 stroke:#00B169, fill:none;
}}
|CAPTION=Schritt 2: Von den unbesuchten Knoten hat E die kürzeste Entfernung zum Startknoten:<br>markiere E als besucht und berechne die Entfernungen zu seinen Nachbarn;<br>es ergeben sich keine Verbesserungen.
|ALIGN=left
|CLASS=noclear}}

{{Thumbnailbox|
INHALT={{#mermaid:graph LR
a(("A (3)"))
b(("B (0)"))
c(("C (4)"))
d(("D (5)"))
e(("E (1)"))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
style b fill:#00B169;
style e fill:#00B169;
style a fill:#00B169;
linkStyle 4 stroke:#00B169, fill:none;
linkStyle 0 stroke:#00B169, fill:none;
}}
|CAPTION=Schritt 3: Von den unbesuchten Knoten hat A die kürzeste Entfernung zum Startknoten:<br>markiere A als besucht und berechne die Entfernungen zu seinen Nachbarn;<br>für Knoten C ergibt sich dadurch eine Verbesserung von 7 auf 4.
|ALIGN=left
|CLASS=noclear}}

{{Thumbnailbox|
INHALT={{#mermaid:graph LR
a(("A (3)"))
b(("B (0)"))
c(("C (4)"))
d(("D (5)"))
e(("E (1)"))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
style b fill:#00B169;
style e fill:#00B169;
style a fill:#00B169;
style c fill:#00B169;
linkStyle 4 stroke:#00B169, fill:none;
linkStyle 0 stroke:#00B169, fill:none;
linkStyle 1 stroke:#00B169, fill:none;
}}
|CAPTION=Schritt 3: Von den unbesuchten Knoten hat C die kürzeste Entfernung zum Startknoten:<br>markiere C als besucht und berechne die Entfernungen zu seinen Nachbarn;<br>es ergeben sich keine Verbesserungen.
|ALIGN=left
|CLASS=noclear}}

{{Thumbnailbox|
INHALT={{#mermaid:graph LR
a(("A (3)"))
b(("B (0)"))
c(("C (4)"))
d(("D (5)"))
e(("E (1)"))
a -- 3 --- b
a -- 1 --- c
b -- 7 --- c
b -- 5 --- d
b -- 1 --- e
c -- 2 --- d
d -- 7 --- e
linkStyle default stroke:lightgray, fill:none;
style b fill:#00B169;
style e fill:#00B169;
style a fill:#00B169;
style c fill:#00B169;
style d fill:#00B169;
linkStyle 4 stroke:#00B169, fill:none;
linkStyle 0 stroke:#00B169, fill:none;
linkStyle 1 stroke:#00B169, fill:none;
linkStyle 3 stroke:#00B169, fill:none;
}}
|CAPTION=Schritt 3: Von den unbesuchten Knoten hat D die kürzeste Entfernung zum Startknoten:<br>markiere D als besucht und berechne die Entfernungen zu seinen Nachbarn;<br>diese sind alle schon besucht worden.
|ALIGN=left
|CLASS=noclear}}
}}

Nun enthält der Graph keine unbesuchten Knoten mehr, der Algorithmus terminiert.

== Weblinks ==

* [https://visualgo.net/en/sssp Visualisierung des Dijkstra-Algorithmus auf VisuAlgo.net 🇬🇧]

[[Kategorie:Graphen]]
[[Kategorie:Algorithmen]]