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

A₀®A₁®A₂ ®… ®A_n

A_k[i][j] – длина пути между вершинами i и j такого, что все промежуточные вершины этого пути принадлежат множеству {1,…,k}.

A_k[i][j] = min{A_k-1[i][j], A_k-1[i][k]+A_k-1[k][j]}

Трудоемкость алгоритма Флойда - O(n³)

Алгоритм. Составляем матрицу в которой на i j месте стоит вес ребра, соединяющего вершины i j и бесконечность если вершины не смежны.

Из нее делаем новую матрицу в которой все элементы по диагонали(бесконечности) и элементы по левому и верхнему краям копируем из исходной матрицы(как бы вычеркиваем как в алгебр дополнение строку и столбец где есть первая по диагонали бесконечность) .

Далее, где ячейки пустые в новой матрице, действуем так – смотрим как бы вычеркнутые строку и столбец где первая бесконечность и смотрим- если сумма в нужном столбце элемента и нужной строке элемента меньше чем текущий элемент в исходной матрице, то присваиваем данной ячейке в новой матрице эту сумму, если же сумма больше текущего элемента в ячейке, то присваиваем этот элемент из исходной матрицы

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