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

Введём некоторые обозначения, перенумеруем вершины исходного графа целыми числами от 1 до n. Обозначим через длину кратчайшего пути из вершины i в вершину j, который в качестве промежуточных может содержать только первые m – вершин графа. Если между вершинами i и j не существует ни одного пути, то будем считать, что . представляет собой кратчайший путь из вершины i в j, не имеющего промежуточных вершин. Для любой вершины i .

Обозначим через матрицу размером , (i, j)-ый элемент которой совпадает с .

Если в исходном графе известна длина каждой дуги, то мы можем сформировать матрицу .

Задача состоит в определении матрицы , представляющей кратчайшие пути между всеми вершинами рассматриваемого графа.

Рассмотрим основную идею, лежащую в основе алгоритма Флойда.

Предположим, что нам известно:

кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование (m-1) первых вершин;
кратчайший путь из вершины m в вершину j, в котором допускается использование в качестве промежуточных (m-1) первых вершин;
кратчайший путь из вершины i в вершину j, в котором в качестве промежуточных допускается использование только (m-1) первых вершин.

Т.к. исходный граф не может содержать контур отрицательной длины, то один из двух путей ― путь, совпадающий с представленным в пункте в), или путь, являющийся объединением путей из пунктов а) и б), ― должен быть кратчайшим путём из вершины i в вершину j, в котором в качестве промежуточных допускается использование только (m-1) первых вершин.

Таким образом, (2)

Из этого соотношения видно, что для вычисления элементов матрицы необходимо располагать лишь элементами матрицы .

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

Определить матрицу , задав величину каждого её элемента (i,j), равную длине кратчайшего пути, соединяющего вершину i с вершиной j.

Если в указанном графе вершины не соединены дугами, то полагается , а все

диагональные элементы равны 0.

Для целого m, последовательно принимающего значения 1, 2, ..., n, определить по величинам элементов матрицы величины элементов матрицы , исследуя соотношения (2).

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

Замечание:

Поскольку , то нет необходимости в вычислении диагональных элементов матриц

Кроме того, для всех i = 1, 2, ..., n имеет место соотношения и . Следовательно, при определении матрицы нет необходимости в пересчёте элементов m- ой строки и m- ого столбца матрицы .