В чём заключается метод Флойда-Уоршелла для построения матрицы кратчайших путей в графе?

Метод Флойда-Уоршелла — это алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. habr.com spravochnick.ru

Главный принцип алгоритма заключается в разделении процедуры нахождения самых коротких путей на отдельные фазы. spravochnick.ru В начале к-той фазы (где к = 1…n) в матрице расстояний хранятся величины самых коротких путей, содержащих как внутренние только вершины из набора {1, 2,…, k – 1}. spravochnick.ru То есть в начале к-той фазы значение d[i][j] равняется величине самого короткого пути между вершинами i и j, при условии, что этот путь содержит только вершины, имеющие номера меньше К (начальная и конечная точка маршрута при этом не учитываются). spravochnick.ru

В первой фазе в матрицу дистанций вписывают матрицу смежности графа: d[i][j]=g[i][j] — цена ребра между вершинами i и j. spravochnick.ru В случае, если есть вершины, не соединённые рёбрами, то необходимо вписать бесконечное значение. spravochnick.ru Расстояние из вершины i в вершину i (то есть в саму себя) необходимо всегда принимать за нуль, это важно для работы алгоритма. spravochnick.ru

В к-той фазе объём работ заключается в переборе всех пар вершин и пересчёте размеров самых коротких путей среди них. spravochnick.ru В итоге по завершению функционирования n-ой фазы, в матрице дистанций d[i][j] окажется размер самого короткого маршрута от i до j, или бесконечность, в случае отсутствия маршрута между вершинами. spravochnick.ru