Jak to działa?

Utrzymuj tablicę dist: dist[source] = 0, a każdemu innemu wierzchołkowi przypisz na początku „nieskończoność” (bardzo dużą liczbę). Dla każdego wierzchołka utrzymuj flagę visited.

Proces krok po kroku:

1. Spośród nieodwiedzonych wierzchołków wybierz ten u, który ma najmniejszą wartość dist. Jeśli żaden nie jest osiągalny, zatrzymaj się.
2. Oznacz u jako odwiedzony: jego odległość jest już ostateczna.
3. Relaksuj każdą krawędź u -> v o wadze w: jeśli dist[u] + w < dist[v], zmniejsz dist[v].
4. Powtarzaj, aż odległości wszystkich osiągalnych wierzchołków będą ostateczne.

Na końcu każdy wierzchołek, którego wartość nadal wynosi nieskończoność, jest nieosiągalny (zwracamy dla niego -1).