Задача о нахождении минимального расстояния между всеми парами вершин. Алгоритм Флойда

Дан ориентированный граф G.

Вес ребра – целое число.

Алгоритм Флойда

Ограничение на граф: в нем не должно быть циклов с отрицательным весом.

Алгоритм заключается в построении квадратных матриц

- матрица расстояний в исходном графе.

Для нахождения самих цепей, а не только их длин, будем строить последовательность матриц

- номер первой вершины в минимальной цепи между iиj вершинами.

Если на каком-либо шаге в матрице С на главной диагонали появилось отрицательное число, значит в графе присутствует цикл с отрицательным весом.

Пример:

Ответ: цепь (1,4): 1→2→3→4.