Алгоритм кратчайших увеличивающих цепей.

 

Этот алгоритм получил наиболее широкое распространение. Он был опубликован в работе Эдмондса и Карпа [5] в 1969 и имеет полиномиальную оценку O(nm²).

Все дуги имеют единичную длину. В качестве увеличивающей цепи выбирается цепь наименьшей длины, при этом не учитывается пропускная способность дуг этой цепи.

 

Пусть q(u,v) – кратчайший путь из u в v. На каждом шаге работы алгоритма, для всех узлов v цепи {s, t} разностной сети, q(u,v) может только возрастать. Назовем дугу (u, v), принадлежащую цепи p разностной сети, критической, если пропускная способность этой дуги равна величине потока, пущенного вдоль p. После увеличения потока вдоль цепи p, эта дуга исчезнет из разностной сети. На каждом шаге определения цепи p хотя бы одна дуга будет критической. В [6] имеется доказательство того, что каждая дуга из E может быть критической не более |V|/2-1 раз. Т.к. мы имеем O(E) пар вершин, соединенных дугами в разностном графе, то общее число критических дуг будет O(EV). Каждая итерация алгоритма Форда-Фалкерсона выполняется за время O(E), следовательно, общая оценка алгоритма кратчайших цепей будет O(mn²).

На практике подобный алгоритм легко реализовать, используя поиск в ширину на первом этапе метода пометок Форда-Фалкерсона.