Come funziona?

Mantieni un array dist: dist[source] = 0 e tutti gli altri vertici iniziano a "infinity" (un numero molto grande). Mantieni un flag visited per ogni vertice.

Procedura passo per passo:

1. Tra i vertici non visitati, scegli quello u con il valore dist più piccolo. Se nessuno è raggiungibile, fermati.
2. Contrassegna u come visitato: la sua distanza è ora definitiva.
3. Rilassa ogni arco u -> v di peso w: se dist[u] + w < dist[v], diminuisci dist[v].
4. Ripeti finché tutti i vertici raggiungibili non sono definitivi.

Alla fine, qualsiasi vertice che è ancora a infinito è irraggiungibile (lo indichiamo con -1).