Алгоритм Флойда: различия между версиями
Материал из Algocode wiki
(Новая страница: «= Алгоритм Флойда = == Постановка == Алгоритм Флойда(-Уоршелла) ищет попарные кратчайшие пу...») |
|||
Строка 10: | Строка 10: | ||
=== База === | === База === | ||
− | + | $ | |
\begin{equation} | \begin{equation} | ||
sp[i][j][k]=\begin{cases} | sp[i][j][k]=\begin{cases} | ||
Строка 17: | Строка 17: | ||
\end{cases} | \end{cases} | ||
\end{equation} | \end{equation} | ||
− | + | $ |
Версия 10:43, 28 ноября 2020
Содержание
Алгоритм Флойда
Постановка
Алгоритм Флойда(-Уоршелла) ищет попарные кратчайшие пути в графе $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} $