Алгоритм Флойда
Материал из Algocode wiki
Версия от 10:43, 28 ноября 2020; Rationalex (обсуждение | вклад)
Содержание
Алгоритм Флойда
Постановка
Алгоритм Флойда(-Уоршелла) ищет попарные кратчайшие пути в графе $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} $