Модификация алгоритма Флойда

Шаг 0. Пусть N = {1, 2, …n}- множество узлов сети. На j-й итерации работы алгоритма будем строить матрицу длин , элемент которой  равен длине «узкого» места (i, j) – цепи, промежуточными узлами в которой могут быть лишь узлы из множества {1, 2,…, p}; и справочную матрицу , каждый элемент которой указывает первый после узла i узел в такой сети.

Алгоритм начинает работу с матрицей , где , если меняется дуга из i в j (в противном случае ), и с матрицей  После построения матриц и  для каждого p=1, 2, …, n, используя для вычислений элементы матриц, полученных на предыдущих итерациях, необходимо выполнить следующую процедуру:

Шаг 1. Пусть матрицы и  найдены. Выделим элементы p-й строки и p-го столбца матрицы . Назовем эти множества элементов базовой строкой и базовым столбцом соответственно.

Шаг 2. Построим матрицы  и , исходя из следующего правила: для

Если , то  и .

Если , то   и .

Шаг 3.  Элемент матрицы  равен «узкому» месту в цепи из узла i в узел j. Элемент  есть узел, стоящий после узла i в этой цепи.