Floyd–Warshall algorithm
Алгоритм Флойда позволяет найти кратчайшее расстояние между любыми двумя вершинами в графе, при этом веса ребер могут быть как положительными, так и отрицательными. Данный алгоритм использует идею динамического программирования.
Будем считать, что в графе n вершин, пронумерованных числами от 0 до n−1. Граф задан матрицей смежности, вес ребра(i−j) хранится в w[i][j]. При отсутствии ребра (i−j) значение w[i][j]=+∞(INF), также будем считать, что w[i][i]=0 (нет петель).
Пусть значение a[k][i][j] равно длине кратчайшего пути из вершины i в вершину j, при этом путь может заходить в промежуточные вершины только с номерами меньшими k (не считая начала и конца пути). То есть a[0][i][j] — это длина кратчайшего пути из i в j, который вообще не содержит промежуточных вершин, то есть состоит только из одного ребра (i−j), поэтому a[0][i][j]=w[i][j] (изначальный вес ребра (i-j)). Значение a[1][i][j]=w[i][j] равно длине кратчайшего пути, который может проходить через промежуточную вершину с номером 0, путь с весом a[2][i][j] может проходить через промежуточные вершины с номерами 0 и 1 и т. д. Путь с весом a[n][i][j] может проходить через любые промежуточные вершины, поэтому значение a[n][i][j] равно длине кратчайшего пути из i в j.
Алгоритм Флойда последовательно вычисляет a[0][i][j], a[1][i][j], A[2][i][j], …, a[n][i][j], увеличивая значение параметра k. Начальное значение, как уже было сказано — a[0][i][j]=w[i][j].
Теперь предполагая, что известны значения a[k-1][i][j] вычислим a[k][i][j]. Кратчайший путь из вершины i в вершину j, проходящий через вершины с номерами, меньшими, чем k может либо содержать, либо не содержать вершину с номером k−1. Если он не содержит вершину с номером k−1, то вес этого пути совпадает с a[k-1][i][j]. Если же он содержит вершину k−1, то этот путь разбивается на две части: от вершины i до вершины k−1 и от вершины k−1 до j. Поэтому, из двух рассматриваемых вариантов необходимо выбрать вариант наименьшей стоимости:
A[k][i][j] = min(A[k — 1][i][j], A[k — 1][i][k — 1] + A[k — 1][k — 1][j]);
Внешний цикл в этом алгоритме последовательно перебирает все вершины, затем пытается улучшить пути из i в j, разрешив им проходить через выбранную вершину.
Упростим этот алгоритм, избавившись от «трехмерности» массива A: будем только хранить значение кратчайшего пути из i в j в A[i][j], а при улучшении пути будем записать новую длину пути также в A[i][j]. Также изменим определение цикла по переменной k, заменив значение k-1 на k.
Очевидно, что сложность такого алгоритма O(n^3 ).
Обратите внимание, что при наличии ребер отрицательного веса значения A[i][j] могут уменьшатся. Поэтому может оказаться, что значение A[i][j] было равно INF, а затем оно уменьшилось благодаря наличию ребер отрицательного веса. В результате значение A[i][j] оказалось меньше INF (например, за счет объединения пути длиной INF и пути отрицательного веса), но при этом все равно пути между вершинами i и j нет. Поэтому нужно либо ставить дополнительные проверки на то, что A[i][k] и A[k][j] не равны INF, либо значения, которые незначительно меньше INF, также считать отсутствием пути.
Алгоритм Флойда некорректно работает при наличии цикла отрицательного веса, но при этом если путь от i до j не содержит цикла отрицательного веса, то вес этого пути будет найден алгоритмом правильно. Также при помощи данного алгоритма можно определить наличие цикла отрицательного веса: если вершина i лежит на цикле отрицательного веса, то значение A[i][i] будет отрицательным после окончания алгоритма.
Восстановление ответа
Для восстановления ответа необходим двумерный массив предшественников. Будем считать, что в Prev[i][j] хранится номер вершины, являющейся предшественником вершины j на кратчайшем пути из вершины i. Тогда при обновлении значения A[i][j] нужно также обновить предшественника. А именно, если путь (i−j) был обновлен на путь, проходящий через вершину k, то теперь предшественником вершины j на пути из i становится вершина, которая была ее предшественником на пути из k, то есть необходимо присвоить Prev[i][j]=Prev[k][j].
Запишем алгоритм, который сохраняет предшественников, а также добавим проверки на существование пути:
Восстановление пути из i в j стандартно, как во всех задачах на динамику:
