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

Тема в разделе "Pascal and Delphi", создана пользователем densi2009, 27 май 2010.

Статус темы:
Закрыта.
  1. densi2009

    densi2009 Гость

    В книжке такое описание и код на Паскале:
    Алгоритм нахождения максимального потока
    Алгоритм определяет максимальный поток в сети, заданной матрицей пропускных способностей дуг. Этот алгоритм использует ту же идею доказательства теоремы Форда и Фалкерсона, а именно, задавшись начальным приближением потока, определяется множество вершин S, которые соединены аугментальными цепями с источником s. Если оказывается, что t принадлежит S, то это означает, что поток не максимальный и его можно увеличить на величину w. Для определения аугментальный цепей и одновременного подсчета величины w в алгоритме использована вспомогательная структура данных:

    Код (Text):
    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 является максимальным и работа алгоритма завершается.

    алгоритмы есть еще здесь
    http://rain.ifmo.ru/cat/view.php/vis/graph...-fulkerson-2008
     
Загрузка...
Статус темы:
Закрыта.

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