госик
Зарегистрирован: 10.10.2006
Сообщения: 9
|
 Добавлено: Вт Окт 10 2006 18:45 Заголовок сообщения: Нахождение максимального потока в сети |
 |
|
В книжке такое описание и код на Паскале:
Алгоритм нахождения максимального потока
Алгоритм определяет максимальный поток в сети, заданной матрицей пропускных способностей дуг. Этот алгоритм использует ту же идею доказательства теоремы Форда и Фалкерсона, а именно, задавшись начальным приближением потока, определяется множество вершин S, которые соединены аугментальными цепями с источником s. Если оказывается, что t принадлежит S, то это означает, что поток не максимальный и его можно увеличить на величину w. Для определения аугментальный цепей и одновременного подсчета величины w в алгоритме использована вспомогательная структура данных:
| Код: |
P : array [1...p] of record
s : enum (-,+) {«знак», то есть напраление дуги}
n : 1.. p {предшествующая вершина в аугментальной цепи}
w : real {величина возможного увеличения потока}
end record
Нахождение максимального потока
Вход: сеть G(V,E) с источником s и стоком t, заданная матрица пропускных способностей C : array [1..p, 1..p] of real.
Выход: матрица максимального потока F : array [1..p, 1..p] of real/
for u, v принадлежащих V do
F[u,v] :=0 {вначале поток нулевой}
end for
M : {итерация увеличения потока}
for v из V do
S[v] :=0; N[v] :=0; P[v] :=(,,) {инициализация}
end for
S[s] :=1; P[s] :=(+,s,бесконечность) {так как s из S}
repeat
a:=0 {признак расширения S}
for v из V do
if S[v] = 1 & N[v] = 0 then
for u из Г(v) do
if S[u] = 0 & F[v,u]<C[v,u] then
S[u] := 1; P[u] :=(+, v, min(P[v].w, C[v,u] – F[v,u])); a :=1
end if
end for
for u из Г^-1(v) do
if S[u] = 0 & F[u,v]>0 then
S[u] :=1; P[u] :=(-, v, min(P[v].w, F[u,v])); a :=1
end if
end for
N[v] :=1
end if
end for
if S[t] then
x :=t; w :=P[t].w
while x не равно s do
if P[x].s = + then
F[P[x].n, x] := F[P[x].n, x] + w
else
F[x, P[x].n] := F[x, P[x].n] – w
end if
x := P[x].n
end while
goto M
end if
until a=0
|
В качестве первого приближения берется нулевой пток, который по определению является допустимым. В основном цикле, помеченном меткой М, делается попытка увеличить поток. Для этого в цикле repeat расширяется, пока это возможно, множество S вершин, достижимых из вершины s по аугментальным цепям. При этом, если в множество S попадает вершина t, то поток вдоль найденной аугментальной цепи (s,t) немедленно увеличивается на величину w, и начинается новая итерация с целью увеличить поток. Процесс расширения множества S в цикле repeat заканчивается, потому что множество вершин конечно, а отмеченные в массиве N вершины повторно не рассматриваются. Если процесс расширения множества S заканчивается и при этом вершина t не попадает в множество S, то по теореме Форда и Фалкерсона найденный поток F является максимальным и работа алгоритма завершается.
Там еще написано, что приведенный алгоритм не является самым эффективным. Может у кого-нибудь есть еще какое решение??? Или как выглядит данный код на С++? Помогите, пожалуйста. |
|
FAQ 
Поиск 
Пользователи 
Группы
Регистрация
Профиль 
Войти и проверить личные сообщения 
Вход 
