Алгоритм Эдмондса-Карпа: различия между версиями
Stasana (обсуждение | вклад) |
Stasana (обсуждение | вклад) м |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 4: | Строка 4: | ||
===Немного теории=== | ===Немного теории=== | ||
− | + | {{Якорь|Лемма о кратчайшем увеличивающем пути}} | |
{{Утверждение | {{Утверждение | ||
|Название=Лемма о кратчайшем увеличивающем пути | |Название=Лемма о кратчайшем увеличивающем пути | ||
Строка 24: | Строка 24: | ||
}} | }} | ||
− | ===Оценка | + | ===Оценка времени работы=== |
− | Каждое ребро может становиться критическим $O(V)$ раз. Суммарно все ребра становятся критическими $O(VE)$ раз. После пускания потока вдоль кратчайшего пути, хотя бы одно ребро становится критическим | + | Каждое ребро может становиться критическим $O(V)$ раз. Суммарно все ребра становятся критическими $O(VE)$ раз. После пускания потока вдоль кратчайшего пути, хотя бы одно ребро становится критическим, значит всего может быть не более $O(VE)$ увеличений потока. Поиск кратчайшего пути мы делаем с помощью $bfs$ следовательно время работы алгоритма $O(VE^2)$. |
{{Автор|Станислав Донской|stasana}} | {{Автор|Станислав Донской|stasana}} |
Текущая версия на 15:53, 4 марта 2020
Данный алгоритм очень похож на алгоритм Форда-Фалкерсона и отличается только тем, что мы будем пускать поток не по произвольному увеличивающему пути, а по кратчайшему. Для этого просто будем вместо $dfs$ использовать $bfs$.
Алгоритм остается корректным по тем же причинам, что и алгоритм Форда-Фалкерсона. Остается только оценить время работы.
Немного теории
Утверждение: (Лемма о кратчайшем увеличивающем пути)
Если $P$ - кратчайший увеличивающий путь в сети G, то после пускания потока вдоль пути $P$, $\forall{v} : d(v) <= d_f(v)$, где $d(v)$ - расстояние от истока до $v$ в сети $G$, а $d_f(v)$ - расстояние от $s$ до $v$ в $G_f$. То есть расстояние не может уменьшиться.
Доказательство:
Рассмотрим вершины, для которых $d > d_f$. Возьмем среди них вершину $v$, с минимальным $d_f$. Тогда существует вершина $u$, что $d_f(u) + 1 = d_f(v)$ и при этом существует ребро $(u, v)$. Это вершина предок $v$ на кратчайшем пути от истока в $G_f$. Так как $d_f(u) < d_f(v)$, а $v$ - вершина с минимальным $d_f$ из тех, для которых $d > d_f$ следует, что $d(u) <= d_f(u)$.
Рассмотрим два случая:
- Ребро $(u, v)$ было в $G$, тогда $d(v) = d(u) + 1 \leq d_f(u) + 1 = d_f(v) \Rightarrow d(v) \leq d_f(v)$ - противоречие
- Ребро $(u, v)$ не было в $G$, но ребро появилось в $G_f$, а значит поток был пущен по ребру $(v, u)$, но мы пускали поток по кратчайшему пути, а значит: $d(v) + 1 = d(u)$. Тогда $d_f(v) < d(v) + 1 = d(u) \leq d_f(u)$, значит $d_f(v) < d_f(u)$, что противоречит $d_f(v) = d_f(u) + 1$ - противоречие
Утверждение: (Лемма о критическом ребре)
Пусть P - кратчайший путь из $s$ в $t$, назовём ребро $(v, u)$ критическим если $c(v, u)$ - минимальна на всем пути $P$. Покажем, что ребро может становится критическим не более $O(V)$ раз.
Доказательство:
Рассмотрим критическое ребро $(v, u)$ принадлежащее кратчайшему пути $P$. Так как $P$ - кратчайший путь $d_0(v) + 1 = d_0(u)$. После пускания потока вдоль $P$ ребро $(v, u)$ пропадает из остаточной сети и что бы оно там появилось снова мы должны пустить поток вдоль обратного ему ребра $(u, v)$. В данном алгоритме мы всегда пускаем поток вдоль кратчайшего пути, а что бы ребро $(u, v)$ принадлежало ему должно выполняться равенство: $d_1(u) + 1 = d_1(v)$. По лемме о кратчайшем увеличивающем пути: $d_0(u) <= d_1(u)$, а значит: $d_0(v) = d_0(u) - 1 <= d_1(u) - 1 = d_1(v) - 2 \Rightarrow d_0(v) <= d_1(v) - 2$, то есть расстояние до $v$ строго увеличилось. Так как расстояние не может превышать $|V|$ ребро $(v, u)$ не может становиться критическим больше чем $O(V)$ раз.
Оценка времени работы
Каждое ребро может становиться критическим $O(V)$ раз. Суммарно все ребра становятся критическими $O(VE)$ раз. После пускания потока вдоль кратчайшего пути, хотя бы одно ребро становится критическим, значит всего может быть не более $O(VE)$ увеличений потока. Поиск кратчайшего пути мы делаем с помощью $bfs$ следовательно время работы алгоритма $O(VE^2)$.
Автор конспекта: Станислав Донской
По всем вопросам пишите в telegram @stasana