нахождение максимального потока в сети

  • Автор темы -
  • Дата начала
Статус
Закрыто для дальнейших ответов.

Гость
#1
В книжке такое описание и код на Паскале:
Алгоритм нахождения максимального потока
Алгоритм определяет максимальный поток в сети, заданной матрицей пропускных способностей дуг. Этот алгоритм использует ту же идею доказательства теоремы Форда и Фалкерсона, а именно, задавшись начальным приближением потока, определяется множество вершин 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 :=1; P :=(+,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 = 0 & F[v,u]<C[v,u] then
S := 1; P :=(+, v, min(P[v].w, C[v,u] – F[v,u])); a :=1
end if
end for
for u из Г^-1(v) do
if S = 0 & F[u,v]>0 then
S :=1; P :=(-, 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 является максимальным и работа алгоритма завершается.

Там еще написано, что приведенный алгоритм не является самым эффективным. Может у кого-нибудь есть еще какое решение??? Или как выглядит данный код на С++? Помогите, пожалуйста.
 
G

goodron

Гость
#3
Конечно, саммый эффективный -- алгоритм Голдберга-Рао : http://algolist.manual.ru/maths/graphs/max...oldberg_Rao.php
Вот вам оценка сложности алгоритмов -- http://algolist.manual.ru/maths/graphs/maxflows/table1.php

А чтобы просмотреть на с++ скачай boost -- там реализован этот алгоритм.
что за boost? тоже очень хочется посмотреть на реализацию этого алгоритма!
 
G

goodron

Гость
#5
Ага, нашел Boost. Нашел документацию.
Нашел "Table of Contents: the Boost Graph Library". В ней есть раздел "Maximum Flow and Matching Algorithms" (Кажется, именно это и нужно. Или не это?). А в этом разделе такие пункты:
1. edmunds_karp_max_flow. Он же Edmonds and Karp O(nm2) 1970 г.
2. push_relabel_max_flow. Он же Goldberg & Tarjan O(nmLog(n2/m)) 1986 г.
3. edmonds_maximum_cardinality_matching
А вот где реализация алгоритма Голдберга-Рао - не нашел. Может ткнете носом в ссылку?
 

Kmet

Well-Known Member
Java Team
25.05.2006
1 036
8
#6
Для: sdriver
предлогать посмотреть пример реализации в бусте новичку в с++... ну ты шутник :)
 
G

goodron

Гость
#8
to sdriver
Есть ли реализация алгоритма Голдберга-Рао в Boost или нет?
 
Статус
Закрыто для дальнейших ответов.