How it works?

Führen Sie ein dist-Array: dist[source] = 0 und jeder andere Knoten beginnt bei „Unendlich“ (einer sehr großen Zahl). Führen Sie ein visited-Flag pro Knoten.

Schritt-für-Schritt-Prozess:

1. Wählen Sie unter den nicht besuchten Knoten denjenigen u mit dem kleinsten dist-Wert aus. Wenn keiner erreichbar ist, stoppen Sie.
2. Markieren Sie u als besucht: Seine Distanz ist nun final.
3. Relaxieren Sie jede Kante u -> v mit dem Gewicht w: Wenn dist[u] + w < dist[v], verringern Sie dist[v].
4. Wiederholen Sie dies, bis alle erreichbaren Knoten finalisiert sind.

Am Ende ist jeder Knoten, der immer noch auf Unendlich steht, unerreichbar (wir geben ihn als -1 an).