53
правки
Изменения
Новая страница: «{{В разработке}} == Алгоритм == Для заданной транспортной сети <tex>G(V, E, c)</tex> алгоритм Эдмондса…»
{{В разработке}}
== Алгоритм ==
Для заданной транспортной сети <tex>G(V, E, c)</tex> алгоритм Эдмондса-Карпа найходит поток максимальной величины из заданной вершины <tex>s</tex> в заданную вершину <tex>t</tex>.
== Псевдокод ==
'''Edmonds_Karp''' (G, s, t)
'''for''' (для) каждого ребра <tex>(u,v) \in E[G]</tex>
'''do''' <tex>f[u,v] \leftarrow 0</tex>
<tex>f[v,u] \leftarrow 0</tex>
'''while''' существует ''кратчайший'' путь <tex>p</tex> из <tex>s</tex> в <tex>t</tex> в остаточной сети <tex>G_f</tex>
'''do''' <tex>c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}</tex>
'''for''' (для) каждого ребра <tex>(u,v) \in p</tex>
'''do''' <tex>f[u,v] \leftarrow f[u,v] + c_f(p)</tex>
<tex>f[v,u] \leftarrow -f[u,v]</tex>
== Корректность алгоритма Эдмондса-Карпа ==
Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона. На каждой итерации цикла '''while''' поток в графе <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> максимальный. Оценка быстродействия будет проведена далее.
{{Лемма
|statement=
Если в транспортной сети <tex>G(V,E)</tex> увеличение потока производиться вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>. То для всех вершин <tex>v \in V[G]\backslash{s,t}</tex> длина кратчайшего пути <tex>\delta_f(s, v)</tex> в остаточной сети <tex>G_f</tex> монотонно возрастает с каждым увеличением потока.
|proof=
Пусть <tex>f<Предположим, что для некоторой вершины <tex>v \in V[G] \backslash {s,t}</tex> существует такое увеличение потока, котрое приводит к уменьшению длины кратчайшего пути.
}}
== Алгоритм ==
Для заданной транспортной сети <tex>G(V, E, c)</tex> алгоритм Эдмондса-Карпа найходит поток максимальной величины из заданной вершины <tex>s</tex> в заданную вершину <tex>t</tex>.
== Псевдокод ==
'''Edmonds_Karp''' (G, s, t)
'''for''' (для) каждого ребра <tex>(u,v) \in E[G]</tex>
'''do''' <tex>f[u,v] \leftarrow 0</tex>
<tex>f[v,u] \leftarrow 0</tex>
'''while''' существует ''кратчайший'' путь <tex>p</tex> из <tex>s</tex> в <tex>t</tex> в остаточной сети <tex>G_f</tex>
'''do''' <tex>c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}</tex>
'''for''' (для) каждого ребра <tex>(u,v) \in p</tex>
'''do''' <tex>f[u,v] \leftarrow f[u,v] + c_f(p)</tex>
<tex>f[v,u] \leftarrow -f[u,v]</tex>
== Корректность алгоритма Эдмондса-Карпа ==
Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона. На каждой итерации цикла '''while''' поток в графе <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> максимальный. Оценка быстродействия будет проведена далее.
{{Лемма
|statement=
Если в транспортной сети <tex>G(V,E)</tex> увеличение потока производиться вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>. То для всех вершин <tex>v \in V[G]\backslash{s,t}</tex> длина кратчайшего пути <tex>\delta_f(s, v)</tex> в остаточной сети <tex>G_f</tex> монотонно возрастает с каждым увеличением потока.
|proof=
Пусть <tex>f<Предположим, что для некоторой вершины <tex>v \in V[G] \backslash {s,t}</tex> существует такое увеличение потока, котрое приводит к уменьшению длины кратчайшего пути.
}}
