Разбор добавил Джафар Исхоков

В основе алгоритма Флойда лежит метод динамического программирования. Пусть A^k - матрица размера NxN с элементами a^k_i,j, где a^k_i,j - длина кратчайшего пути

между вершинами i и j, проходящего через вершины с номерами меньше либо равными k (не считая начальной и

конечной вершин). Тогда A⁰ - матрица смежности нашего графа, Aⁿ - искомая матрица кратчайших расстояний.

Найдем a^k_i,j, зная A^k-1. Заметим, что в кратчайшем пути между вершинами i и j, содержащем вершины с номерами от 1 до k

(т.е. соответсвующем a^k_i,j) вершина k может либо встречаться, либо нет. Значит a^k_i,j = min(a^k-1_i,j , a^k-1_i,k + a^k-1_k,j).

Один из вариантов реализации алгоритма Флойда выглядит так:
   for k := 1 to n do
     for i := 1 to n do
       for j := 1 to n do
         if a[k,i,j] > a[k-1,i,k] + a[k-1,k,j] then
           a[k,i,j] := a[k-1,i,k] + a[k-1,k,j];

Пусть у нас есть кратчайший путь из вершины i в вершину k. Заметим тогда, что в этом пути вершина k

не может встречаться среди промежуточных вершин. Действительно, пусть это не так, тогда в нашем

графе найдется цикл отрицательного веса, а этого по условию быть не может.

В наших обозначениях это выглядит так: a[k,i,k]=a[k-1,i,k] и a[k,k,j]=a[k-1,k,j] для любых i и j. Значит алгоритм Флойда можно изменить следующим образом:
   for k := 1 to n do
     for i := 1 to n do
       for j := 1 to n do
         if a[i,j] > a[i,k] + a[k,j] then
           a[i,j] := a[i,k] + a[k,j];