Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину — различия между версиями
(Новая страница: «Алгоритм Форда — Фалкерсона — алгоритм, решающий задачу нахождения максимального потока…») |
|||
| Строка 2: | Строка 2: | ||
== Идея == | == Идея == | ||
| − | Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: <tex> f(u,v) = 0 </tex> для всех <tex> u, v </tex> из <tex> V </tex>. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь. | + | Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: <tex> f(u,v) = 0 </tex> для всех <tex> u, v </tex> из <tex> V </tex>. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью [[Обход в глубину, цвета вершин|обхода в глубину (dfs)]]. Процесс повторяется, пока можно найти увеличивающий путь. |
== См. также == | == См. также == | ||
* [[Теорема Форда-Фалкерсона]] | * [[Теорема Форда-Фалкерсона]] | ||
Версия 23:12, 21 декабря 2010
Алгоритм Форда — Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.
Идея
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: для всех из . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.
