Алгоритм Эдмондса-Карпа, кратчайших увеличивающих цепей

Опубликовано: 12.10.2017

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

 

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

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

 

Пусть 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 2).

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

 

rss