The Dijkstra Algorithm

Der Dijkstra-Algorithmus ist ein Algorithmus zur Bestimmung des kürzesten Pfades von einem Startknoten zu allen anderen Knoten in einem gewichteten Graphen. Er arbeitet dabei mit einer Prioritätswarteschlange, in der die Knoten nach ihrer Entfernung zum Startknoten sortiert sind. Der Algorithmus besucht jeden Knoten nur einmal und aktualisiert dabei laufend die Entfernungen zu den Nachbarknoten.

Hier sind die Schritte des Dijkstra-Algorithmus:

1. Initialisierung: Setze die Entfernung zum Startknoten auf 0 und die Entfernung zu allen anderen Knoten auf unendlich. Füge den Startknoten zur Prioritätswarteschlange hinzu.
2. Solange die Prioritätswarteschlange nicht leer ist, nimm den Knoten mit der kürzesten Entfernung aus der Prioritätswarteschlange.
3. Für jeden Nachbarknoten des aktuellen Knotens, berechne die Entfernung zum Startknoten durch Addition der Entfernung vom aktuellen Knoten zum Nachbarn und der Entfernung vom Startknoten zum aktuellen Knoten. Falls diese Entfernung kürzer ist als die aktuelle Entfernung zum Nachbarn, aktualisiere die Entfernung und füge den Nachbarn zur Prioritätswarteschlange hinzu.
4. Wiederhole Schritt 2 und 3, bis alle Knoten besucht wurden.

Am Ende des Algorithmus enthält jeder Knoten die Entfernung zum Startknoten und der kürzeste Pfad kann durch Rückverfolgung dieser Entfernungen ermittelt werden.