Dijkstra-Algorithmus

Ein Beispielgraph

Der Dijkstra-Algorithmus ist ein Algorithmus zum Finden kürzester Wege in einem gewichteten 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.

1. Markiere alle Knoten des Graphen als noch nicht besucht.
2. 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 $\infty$ gesetzt.
3. Solange es noch unbesuchte Knoten mit einer Entfernung $<\infty$ gibt, führe folgende Schritte aus:
   1. Wähle einen unbesuchten Knoten $v$ mit der kürzesten Entfernung zum Startknoten aus.
   2. Markiere $v$ als besucht.
   3. Betrachte nun alle Nachbarknoten $u$ von $v$:
      1. Wenn die Entfernung von $u$ zum Startknoten größer ist als die Entfernung vom Startknoten zu $v$ plus die Länge der Kante zwischen $u$ und $v$, dann setze die Entfernung von $u$ zum Startknoten auf die Entfernung vom Startknoten zu $v$ plus die Länge der Kante zwischen $u$ und $v$

Beispiel

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

Vorbereitung: Startknoten B erhält Entfernung 0,
alle anderen Knoten erhalten Entfernung $\infty$.

Schritt 1: markiere B als besucht und berechne für alle seine Nachbarn die Entfernung zu B.

Schritt 2: Von den unbesuchten Knoten hat E die kürzeste Entfernung zum Startknoten:
markiere E als besucht und berechne die Entfernungen zu seinen Nachbarn;
es ergeben sich keine Verbesserungen.

Schritt 3: Von den unbesuchten Knoten hat A die kürzeste Entfernung zum Startknoten:
markiere A als besucht und berechne die Entfernungen zu seinen Nachbarn;
für Knoten C ergibt sich dadurch eine Verbesserung von 7 auf 4.

Schritt 3: Von den unbesuchten Knoten hat C die kürzeste Entfernung zum Startknoten:
markiere C als besucht und berechne die Entfernungen zu seinen Nachbarn;
es ergeben sich keine Verbesserungen.

Schritt 3: Von den unbesuchten Knoten hat D die kürzeste Entfernung zum Startknoten:
markiere D als besucht und berechne die Entfernungen zu seinen Nachbarn;
diese sind alle schon besucht worden.

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

Weblinks

• Visualisierung des Dijkstra-Algorithmus auf VisuAlgo.net 🇬🇧

Algorithmen auf Graphen

Suche: Breitensuche | Tiefensuche

Kürzeste Wege: Dijkstra-Algorithmus | Bellman-Ford-Algorithmus

Minimale Spannbäume: Kruskal-Algorithmus | Prim-Algorithmus | Borůvka-Algorithmus