Einleitung 
Der Dijkstra Algorithmus ist ein Verfahren aus der Graphentheorie, das zur Bestimmung des kürzesten Pfades in einem gewichteten Graphen eingesetzt wird. Der Algorithmus wurde von dem niederländischen Informatiker Edsger W. Dijkstra entwickelt und erstmals 1959 veröffentlicht.
Prinzip
Der Dijkstra Algorithmus arbeitet mit einem gewichteten Graphen, bei dem jedem Knoten ein Kostenwert zugeordnet ist. Das Ziel des Algorithmus ist es, den kürzesten Pfad von einem Startknoten zu allen anderen Knoten im Graphen zu finden. Dabei werden die Kosten der Pfade schichtweise aktualisiert, bis alle Knoten erreicht wurden.
- Initialisierung: Setze die Distanz zum Startknoten auf 0 und zu allen anderen Knoten auf unendlich.
- Iterative Verarbeitung:
- Wähle den Knoten mit der aktuell kleinsten bekannten Distanz.
- Für jeden Nachbarn dieses Knotens:
- Berechne die Gesamtdistanz vom Start über den aktuellen Knoten zum Nachbarn.
- Falls diese Distanz kürzer ist als die bisher bekannte, aktualisiere sie.
- Abbruch: Wenn alle Knoten bearbeitet wurden oder das Ziel erreicht ist.