Введение
Нам дан ориентированный или неориентированный взвешенный граф с вершинами. Нам нужно найти кратчайшее расстояние между каждой парой вершин и .
Граф может содержать рёбра с отрицательными весами, но он не должен содержать циклов отрицательного веса.
Этот алгоритм также можно использовать для обнаружения отрицательных циклов: если после завершения алгоритма мы получим