Изменения

Перейти к: навигация, поиск

Алгоритм Эдмондса-Карпа

15 байт добавлено, 22:14, 5 декабря 2015
Корректность алгоритма Эдмондса-Карпа
== Корректность алгоритма Эдмондса-Карпа ==
Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]]. На каждой итерации цикла '''<tex>\mathrm {while''' }</tex> поток в графе <tex>G</tex> увеличивается вдоль одного из кратчайших путей в <tex>G_f</tex> из истока <tex>s</tex> в сток <tex>t</tex>. Этот процесс повторяется до тех пор пока существует кратчайший <tex>s \leadsto t</tex> путь в <tex>G_f</tex>. Если в <tex>G_f</tex> не существует кратчайшего пути из <tex>s</tex> в <tex>t</tex>, значит, не существует никакого вообще никакого <tex>s \leadsto t</tex> пути в <tex>G_f</tex> следовательно по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] найденный поток <tex>f</tex> максимальный.
== Оценка быстродействия ==
Анонимный участник

Навигация