How it works?

Поддерживайте массив dist: dist[source] = 0, а все остальные вершины изначально имеют значение «бесконечность» (очень большое число). Поддерживайте флаг visited для каждой вершины.

Пошаговый процесс:

1. Среди непосещенных вершин выберите ту u, у которой значение dist минимально. Если ни одна вершина не достижима, остановитесь.
2. Отметьте u как посещенную: ее расстояние теперь окончательно.
3. Релаксируйте каждое ребро u -> v весом w: если dist[u] + w < dist[v], уменьшите dist[v].
4. Повторяйте до тех пор, пока все достижимые вершины не будут обработаны.

В конце любая вершина, значение которой осталось равным бесконечности, считается недостижимой (мы возвращаем для нее -1).