37
правок
Изменения
Новая страница: «Алгоритм Форда — Фалкерсона — алгоритм, решающий задачу нахождения максимального потока…»
Алгоритм Форда — Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.
== Идея ==
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 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, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.
== См. также ==
* [[Теорема Форда-Фалкерсона]]
