Dijkstra Algorithmus


Mit dem Algorithmus von Dijkstra kann der kürzeste Weg zwischen zwei Knoten
in einem gewichteten, zusammenhängenden Graph berechnet werden.
Solche Berechnungen kennen wir von Navigationsgeräten. Sie berechnen den kürzesten Weg zwischen zwei Orten.
In der Station Graphentheorie wird der Algorithmus verwendet,
um den kürzesten Weg zwischen den beiden Knoten ungeraden Grades zu bestimmen.

1. Schritt: Suche den Startknoten.

2 .Schritt: Suche alle Nachbarknoten zum Startknoten und betrachte ihre Distanz

3. Schritt: Wähle den Knoten mit der geringsten Distanz zum Startknoten. Er wird nun aktiver Knoten.

4. Schritt: Suche von diesem Knoten aus wieder alle Nachbarknoten, die noch nicht aktive Knoten waren.

5. Schritt: Berechne deren Distanz. Die Distanz berechnet sich aus
der Distanz des aktiven Knotens + des Kantengewichtes der verbindenden Kante.

6. Schritt: Ist die neu berechnete Distanz für einen Knoten kleiner als die bestehende wird sie gelöscht
und die neue Distanz festgeschrieben. Der aktive Knoten wird als Vorgänger dieses Knoten gespeichert.

7. Schritt: Wähle einen Knoten mit minimaler Distanz. Dieser wird nun aktiver Knoten.

8. Schritt: Die Schritte 3- 7 werden solange wiederholt, bis alle Knoten eine unveränderliche Distanz besitzen.

(Hußmann 2007, S. 27- 32)