Графы для самых маленьких: Ford & Bellman или как понять, что ты попал в бесконечно далекое прошлое

Стоило бы указать, что «фишка» Форда-Беллмана именно в умении корректно отрабатывать отрицательные веса.

Если же в графе таких нет (как например метрополитен на картинке) то более уместен алгоритм Дейкстры, работающий за O(E log V).

Ну и по-старинке визуализаторы этого и других алгоритмов rain.ifmo.ru/cat/view.php/vis/graph-paths