|
Алгоритм Эдмондса — КарпаАлгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время O(VE2). Впервые был опубликован в 1970 году советским учёным Е. А. Диницом. Позже, в 1972 году, был независимо открыт Эдмондсом и Карпом. А.Э.-К. — это вариант алгоритма Форда — Фалкерсона, при котором на каждом шаге выбирают кратчайший дополняющий путь из s в t в остаточной сети (полагая, что каждое ребро имеет единичную длину). Кратчайший путь находится поиском в ширину.
Чтобы найти кратчайший путь в графе, используем поиск в ширину:
В процессе работы А.Э.-К. будет находить каждый дополняющий путь за время O(E). Ниже мы докажем, что общее число увеличений потока, выполняемое данным алгоритмом, составляет O(VE). Таким образом, сложность А.Э.-К. равна O(VE2). Назовём расстоянием от вершины x до вершины у длину кратчайшего пути от x до y в остаточной сети. Если такого пути нет, будем считать расстояние бесконечным. Будем говорить, что y приблизилась к x (отдалилась от x), если расстояние от x до y уменьшилось (увеличилось). Будем говорить, что y ближе к x (дальше от x), чем z, если расстояние от x до y меньше (больше), чем расстояние от x до z. Лемма. В ходе работы алгоритма ни одна вершина никогда не приближается к источнику. Доказательство. Пусть это не так, тогда при каком-то увеличении потока некоторые вершины приблизилась к источнику. Назовём их неправильными. Выберем ту из неправильных вершин, которая после увеличения потока оказалась ближе всех к источнику (если таких больше одной, то любую из них). Обозначим выбранную вершину через v. Рассмотрим кратчайший путь от s до v. Обозначим предпоследнюю вершину на этом пути через u, таким образом, путь имеет вид s-...-u-v. Поскольку u ближе к s, чем v, а v - ближайшая к s из неправильных вершин, u - вершина правильная. Обозначив расстояния от s до u и v до и после увеличения потока соответственно через , , , , имеем:
, откуда
Следовательно, до увеличения потока ребро (u, v) отсутствовало в остаточной сети. Чтобы оно появилось, увеличивающий путь должен был содержать ребро (v, u). Но в А.Э.-К. увеличивающий путь всегда кратчайший, следовательно, du = dv + 1 , что противоречит предыдущему неравенству. Значит, наше предположение было неверным. Лемма доказана. Назовём критическим то из ребёр увеличивающего пути, у которого остаточная пропускная способность минимальна. Оценим, сколько раз некое ребро (u, v) может оказываться критическим. Пускай это произошло на итерации t1, а в следующий раз на итерации t2. Обозначая через Dy(t) расстояние от s до y на итерации t, имеем: Dv(t1) = Du(t1) + 1 Dv(t2) = Du(t2) + 1 Заметим, что критическое ребро исчезает из остаточной сети. Чтобы ребро (u, v) в ней вновь появилось, необходимо, чтобы на какой-то промежуточной итерации t3 был выбран увеличивающий путь, содержащий ребро (v, u). Следовательно, Du(t3) = Dv(t3) + 1 Используя ранее доказанную лемму, получаем:
Поскольку изначально Dv > 0 (иначе v=s, но ребро, ведущее в s, не может появиться на кратчайшем пути из s в t), и всегда, когда Dv конечно, оно не превышает V (кратчайший путь не содержит циклов, и, следовательно, содержит менее V ребёр), ребро может оказаться критическим не более раз. Поскольку каждый увеличивающий путь содержит хотя бы одно критическое ребро, а всего рёбер, которые могут когда-то стать критическими, 2E (все рёбра исходной сети и им противоположные), то мы можем увеличить путь не более Е(V+2) раз. Следовательно, количество итераций не превышает O(EV), что и требовалось доказать. Пусть задана сеть с истоком в вершине A и стоком в вершине G. На рисунке парой f / c обозначен поток по этому ребру и его пропускная способность. Опишем поиск в ширину на первом шаге.
Заметим, что в очередь последовательно добавляли вершины, достижимые из A ровно за 1 шаг, ровно за 2 шага, ровно за 3 шага. Кроме того, предком каждой вершины является вершина, достижимая из A ровно на 1 шаг быстрее.
Отметим, что в процессе выполнения алгоритма длины дополняющих путей (на рисунках обозначены красным) не убывают. Это свойство выполняется благодаря тому, что мы ищемкратчайший дополняющий путь. Улучшенной версией А.Э.-К. является алгоритм Диница, требующий O( | V | 2 | E | ) операций. Назовём вспомогательной бесконтурной сетью графа G с источником s его подграф, содержащий только такие рёбра (u, v), для которых минимальное расстояние от s до v на единицу больше минимального расстояния от s до u. Алгоритм Диница:
|
Loading
|