How it works?

Conservez un tableau dist : dist[source] = 0 et tous les autres sommets commencent à "l'infini" (un nombre très grand). Conservez un indicateur visited par sommet.

Processus étape par étape :

1. Parmi les sommets non visités, choisissez celui u ayant la plus petite valeur dist. Si aucun n'est accessible, arrêtez-vous.
2. Marquez u comme visité : sa distance est désormais finale.
3. Relâchez chaque arête u -> v de poids w : si dist[u] + w < dist[v], diminuez dist[v].
4. Répétez jusqu'à ce que tous les sommets accessibles soient finalisés.

À la fin, tout sommet toujours à l'infini est inaccessible (nous le signalons par -1).