Dijkstra: Algorithmus anwenden

Dijkstra bestimmt kürzeste Wege in gewichteten Graphen mit nichtnegativen Kantengewichten. Unbekannte Entfernungen beginnen bei +∞, der Start bei 0. Immer wird der unbesuchte Knoten mit dem kleinsten vorläufigen Wert gewählt. Für jeden unbesuchten Nachbarn wird geprüft, ob der Weg über den aktuellen Knoten kürzer ist. Sein neuer Wert ist das Minimum aus bisherigem Wert und aktueller Entfernung plus Kantengewicht.

Dieses Greedy-Verfahren liefert unter dieser Voraussetzung garantiert kürzeste Wege. Ein Knoten in besucht erhält keinen neuen Wert mehr; unmittelbar nach seiner Aufnahme werden seine unbesuchten Nachbarn geprüft.