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

Источник:
  Электронный учебник по информатике,
  школа №9 им. А.С.Пушкина, г.Пермь
  http://school9.perm.ru/Tutorial/Graph/chapter2/shortest_way/floyd.htm

Иногда называется так же алгоритмом Флойда-Уоршолла.

Этот алгоритм ищет кратчайшие расстояния между каждой парой вершин во взвешенном графе за время O(N³) для графа, заданного матрицей смежности. Если граф задан списком рёбер, то для его реализации потребуется потратить дополнительно O(M) времени на формирование матрицы смежности, т.к. алгоритм работает только при таком представлении.

Для его реализации нам потребуется помимо матрицы смежности A только матрица кратчайших расстояний P: array[1..MaxN, 1..MaxN] of Integer.

Алгоритм работает N итераций, причём на K-ой итерации в элементе P[I, J] хранится длина такого кратчайшего пути из I-ой вершины в J-ую, который использует в качестве промежуточных вершин только вершины с номером не более K. Т.о. после отработки N итераций в массиве P будут храниться все кратчайшие пути, использующие в качестве промежуточных вершин вершины с номером не более N, т.е. просто все кратчайшие пути. В этом случае алгоритм может выглядеть так (здесь I, J, K: Integer):

Не правда ли, потрясающе красивый и простой алгоритм? А главное, он легко запоминается и почти не имеет модификаций.

В строке 1 происходит инициализация матрицы кратчайших расстояний. Изначально она совпадает с матрицей смежности. После этого в течение N итераций по K (строка 2) мы пытаемся улучшить кратчайшие расстояния между каждой парой вершин I и J (строки 3-4), добавляя в качестве возможной промежуточной вершины вершину с номером K (строка 5).

Обратите внимание на то, что после первой строки мы совершенно не используем массив A. Это значит, что, если нам после отработки алгритма не нужна матрица смежности в чистом виде, то мы можем не пользоваться дополнительным массивом P и не терять лишние O(N²) памяти, а все изменения проводить сразу в массиве A. На практике так обычно и бывает. В этом случае, получается, алгоритм потребляет O(1) дополнительной памяти.

Подобно алгоритму Форда-Беллмана, алгоритм Флойда может определить наличие в графе циклов отрицательного веса. Если они есть, то после его отработки на диагонале матрицы кратчайших путей возникнут отрицательные числа. Действительно, кратчайшее расстояние от вершины в этом цикле до неё самой будет меньше нуля, что будет соответствовать проходу по этому циклу.

Подобно всё тому же алгоритму Форда-Беллмана, если конечное значение некоторого элемента матрицы больше чем Inf - MinW * (MaxN - 1), то между двумя соответствующими вершинами не существует кратчайшего пути. Аналогичны рассуждения и для некорректности такого замечания при Inf <= (MinW + MaxW) * (MaxN - 1)

Кстати, не забивайте себе голову всеми этими способами определения отрицательных циклов и предельными значениями Inf-ов, это Вам вряд ли понадобится. Постарайтесь просто осознать суть, понять, откуда взялись эти ограничения. А откуда? А из максимально возможной длины кратчайшего пути.