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

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

Постановка

Алгоритм Флойда(-Уоршелла) ищет попарные кратчайшие пути в графе $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][k]=\begin{cases} w(i, j), & \text{если $(i, j) \in E$}.\\ 0, & \text{иначе}. \end{cases} \end{equation} $$