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

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

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

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