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

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

Постановка

Алгоритм Флойда(-Уоршелла) ищет попарные кратчайшие пути в графе $G = (V, E)$ без отрицательных циклов. В случае наличия в графе отрицательных циклов, алгоритм может вернуть один из них.

Решение с помощью динамического программирования

Пусть все вершины в графе пронумерованы от $1$ до $n$, а вес ребра между вершинами $i$ и $j$ равен $w(i, j)$.

Определение

Введём динамическое программирование $sp[i][j][k]$ --- длина кратчайшего пути в графе между вершинами $i$, и $j$, при условии, что все \bf{промежуточные} вершины имеют номера, не превосходящие $k$. Обратите внимание, что на $i$ и $j$ это ограничение не распространяется.

База

$ \begin{equation} sp[i][j][0]=\begin{cases} w(i, j), & \text{если $(i, j) \in E$}.\\ 0, & \text{иначе}. \end{cases} \end{equation} $

Пересчёт

На $k$-м уровне динамического программирования, мы разрешаем путям между вершинами посещать вершину с номером $k$. От этого пути между какими-то $i$ и $j$ могли сократиться за счёт прохода по пути $i ~- k$, а затем по $k ~- j$.

Таким образом, формула пересчёта устроена следующим образом ($k \geq 1$): $ \begin{equation} sp[i][j][k]=min\begin{cases} sp[i][j][k - 1]\\ sp[i][k][k - 1] + sp[k][j][k - 1] \end{cases} \end{equation} $