Dijkstra Algorithmus

Der Algorithmus von Dijkstra berechnet in einem ungerichteten, gewichteten Graphen den Kürzest Weg von einem Punkt (s) zu einem anderen Punkt (t). Dabei werden ausgehend vom Start immer alle angrenzenden Wege untersucht. Ziel ist es sich solang durch den Graphen zu „hangeln“ bis jeder Knoten markiert wurde. Damit ist sichergestellt, dass alle möglichen Wege untersucht wurden.
Wird ein neuer kürzester Weg zwischen 2 Knoten gefunden, wird der so gefundene Knoten für den nächsten Schritt ausgewählt. Findet der Algorithmus so eine Verbindung zwischen 2 Knoten, die kürzer ist als eine bereits bekannte wird diese verwendet, andernfalls wird die Verbindung verworfen.

Aus der Tabelle können nun auch die kürzesten Verbindungen vom Start zu jedem
anderen Knoten abgelesen werden (unterstrichene Werte):

• s-b: 2
• s-c: 8
• s-d: 11
• s-e: 7
• s-t: 14

Erklärung

1. im Schritt 1 wird der Baum initialisiert. Vom Startpunkt aus kann nur zu sich selbst gegangen werden, die anderen Punkte sind nicht erreichbar (∞)
2. Im 2. Schritt werden alle Verbindungen vom Knoten s gesucht und der Weg mit der kürzesten Entfernung gewählt b. Damit enthält die Menge der ungefärbten Knoten T (Restknoten) zu diesem Zeitpunkt alle außer dem Startknoten selbst.
3. Im 3. Schritt ist b nicht mehr Teil der ungefärbten Knoten. Es wird nun geprüft zu welchen Knoten gegangen werden kann. Dabei ist der Weg s-c genau so weit wie s-b-c.
4. Analog zu 3.
5. Analog zu 3.
6. Bei Schritt 4 wurde c als Knoten gewählt. Der Weg s-c-d ist mit der Länge 11 kürzer, als der bereits bekannte Weg s-b-e-d (12). Daher ändert sich hier der Wert im Vergleich zu Schritt 4.

Dijkstra Algorithmus in der Wikipedia