Алгоритм Флойда-Уоршела

Этот алгоритм в отличии от предыдущих двух находит кратчайшие пути сразу для всех пар узлов. Если в алгоритме Беллмана-Форда итерируется число дуг в пути, а в алгоритме Дийкстра – длина пути, то в алгоритме Флойда-Уоршела итерируется множества узлов, которые допускается иметь в качестве промежуточных узлов на путях. Как и оба других алгоритма. Алгоритм Флойда-Уоршела начинается с расстояний из одной дуги (т.е. без промежуточных узлов),выбранных в качестве исходных оценок для длин кратчайших путей. Затем вычисляются кратчайшие пути с тем ограничением, что промежуточным узлом может быть только узел 1,затем с ограничением, что промежуточными узлами могут быть только узлы 1 и 2 и т.д.

Для более строгого описания алгоритма обозначим через

Длину кратчайшего пути от узла i к узлу j при ограничении, что только узлы 1,2,…, n могут использоваться в качестве промежуточных узлов на пути. Алгоритм при этом работает следующим образом.

Сначала = для всех i,j,i≠j.

Для n=0,1,…,N-1,

для всех i≠j.

Объём вычисления по данному алгоритму оценивается величиной 0(),т.е. он такой же, как и алгоритм Дийкстра повторённого для всех узлов, выбранных в качестве источника.