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

Тема в разделе "MS Visual C++", создана пользователем -, 10 окт 2006.

Статус темы:
Закрыта.
  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 является максимальным и работа алгоритма завершается.

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

    sdriver Гость

  3. goodron

    goodron Гость

    что за boost? тоже очень хочется посмотреть на реализацию этого алгоритма!
     
  4. European

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    <!--QuoteBegin-goodron+17:08:2007, 08:33 -->
    <span class="vbquote">(goodron @ 17:08:2007, 08:33 )</span><!--QuoteEBegin-->что за boost?
    [snapback]75546" rel="nofollow" target="_blank[/snapback]​
    [/quote]
    BOOST на Википедии
     
  5. goodron

    goodron Гость

    Ага, нашел 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
    А вот где реализация алгоритма Голдберга-Рао - не нашел. Может ткнете носом в ссылку?
     
  6. Kmet

    Kmet Well-Known Member

    Регистрация:
    25 май 2006
    Сообщения:
    1.017
    Симпатии:
    1
    Для: sdriver
    предлогать посмотреть пример реализации в бусте новичку в с++... ну ты шутник :)
     
  7. goodron

    goodron Гость

    Тем более несуществующий...
     
  8. goodron

    goodron Гость

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

Поделиться этой страницей