Maksymalny przepływ w sieci – algorytmy Forda-Fulkersona i Edmondsa-Karpa


Tematy pokrewne   Podrozdziały
Sieci przepływowe
Podstawowe pojęcia dotyczące sieci przepływowych
Maksymalny przepływ w sieci – algorytmy Forda-Fulkersona i Edmondsa-Karpa
Znajdowanie maksymalnych skojarzeń za pomocą wyznaczania maksymalnego przepływu

Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Podstawowe pojęcia dotyczące kolejek
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Znajdowanie ścieżki w grafie

  Algorytm Forda-Fulkersona
Algorytm Edmondsa-Karpa

Problem

Dla danej sieci przepływowej określić jej maksymalny przepływ.

 

 

Algorytm Forda-Fulkersona

Naturalnym problemem wyłaniającym się w sieciach przepływowych jest problem maksymalnego przepływu (ang. maximum flow problem). W problemie tym musimy określić maksymalną wielkość przepływu ze źródła do ujścia sieci przy ograniczeniach przepustowości nałożonych na poszczególne kanały.

Problem wyznaczania maksymalnego przepływu rozwiązuje algorytm Forda-Fulkersona. Opiera się on na idei sieci rezydualnych (ang. residual network) oraz ścieżek rozszerzających (ang. augmenting path). Sieć rezydualna powstaje z sieci przepływowej przez zastąpienie przepustowości kanałów przepustowościami rezydualnymi wyliczanymi wg poniższego wzoru:

 

cf(u,v) = c(u,v) - f(u,v)

Gdzie:

cf  –  przepustowość rezydualna (ang. residual capacity)
c  –  przepustowość kanału (ang. capacity)
f  –  przepływ w kanale (ang. flow), a u i v są węzłami sieci przepływowej połączonymi kanałem, dla którego wyznaczamy przepustowość rezydualną

 

Ponieważ w odwrotnym kierunku również występuje przepływ (ujemny), w sieci rezydualnej mogą pojawiać się dodatkowe kanały skierowane przeciwnie do kanałów pierwotnych. Dla kanałów przeciwnych przepustowość rezydualna wyraża się wzorem:

 

cf(v,u) = f(u,v)

 

czyli jest równa przepływowi w kanale pierwotnym. Uzasadnienie jest bardzo proste – ponieważ w sieci pierwotnej nie istnieje kanał łączący wierzchołki v i u (istnieje tylko kanał od u do v), to jego przepustowość c(v,u) jest równa 0, co wynika bezpośrednio z definicji przepustowości. Z kolei z własności skośnej symetryczności przepływu otrzymujemy, iż f(v,u) = -f(u,v). Zatem:

 

cf(v,u) = c(v,u) – f(v,u) = 0 – (-f(u,v) = f(u,v)

 

Ścieżka rozszerzająca jest ścieżką w sieci rezydualnej (to ważne – w pierwotnej sieci takiej ścieżki może nie być!!!) łączącą źródło s z ujściem t. Wszystkie kanały leżące na ścieżce rozszerzającej muszą posiadać niezerowe przepustowości rezydualne. Przepustowość rezydualna ścieżki rozszerzającej jest równa najmniejszej przepustowości rezydualnej kanałów należących do tej ścieżki. Fakt ten zapisujemy następująco:

 

cf(p) = min{cf(u,v): (u,v) symbol p}

 

Warunek ten jest bardzo łatwy do zrozumienia – ścieżka rozszerzająca służy do powiększania przepływu wzdłuż zawartych w niej kanałów. Powiększony przepływ będzie przepływał przez każdy z kanałów na ścieżce, dlatego można go powiększyć tylko o tyle, ile wynosi najmniejsza przepustowość rezydualna kanałów ścieżki.

 

Podstawowy algorytm Forda-Fulkersona brzmi następująco:

 

Wyzeruj wszystkie przepływy w sieci

Dopóki w sieci rezydualnej istnieje ścieżka rozszerzająca p, zwiększaj przepływ o cf(p) wzdłuż kanałów zgodnych z kierunkiem ścieżki, a zmniejszaj przepływ wzdłuż kanałów przeciwnych (wygaszanie przepływu). Przepływ sieciowy rośnie o cf(p).

 

Aby lepiej zrozumieć ten algorytm, oprzyjmy się na prostym przykładzie.

 

Oto nasza sieć przepływowa. W kanałach zaznaczyliśmy ich przepustowości. Przepływy netto są zerowe.

Również przepływ sieci

| f | = 0.

Dla zerowych przepływów sieć rezydualna jest identyczna z siecią pierwotną. Szukamy w niej ścieżki rozszerzającej, która połączy źródło s z ujściem t. Takich ścieżek może być wiele. Umówmy się, że wybieramy najkrótszą z nich (mającą najmniej krawędzi).

Na przykład może to być ścieżka: p = {s→A→B→t}

Na ścieżce p znajdują się trzy kanały sieci rezydualnej: (s,A), (A,B) i (B,t). Przepustowość rezydualna cf(p) ścieżki jest równa najmniejszej przepustowości rezydualnej jej kanałów. Najmniejszą przepustowość rezydualną posiada kanał (B-t), dla którego cf(B,t) = 6. Zatem wzdłuż krawędzi ścieżki przepływ można zwiększyć o 6 jednostek. O tyle rośnie również przepływ sieciowy, czyli

| fnowy | = | fstary | + cf(p) = 0 + 6 = 6

Zwiększenie przepływu w kanale sieci pierwotnej o cf(p) odpowiada zmniejszeniu przepustowości rezydualnej tego kanału. Jednocześnie wraz z pojawieniem się przepływu w kanale sieci pierwotnej powstaje kanał przeciwny w sieci rezydualnej o przepustowości rezydualnej równej przepływowi.

Przepustowość rezydualna kanału (s,A) wynosi 3 – oznacza to, iż kanałem tym można wciąż jeszcze przesłać trzy dodatkowe jednostki przepływu. Zwróć uwagę, iż w siei rezydualnej pojawił się kanał przeciwny (A,s) o przepustowości rezydualnej cf(A,s) = 6.

Kanał (A,B) może jeszcze przesłać 1 dodatkową jednostkę przepływu. Również tutaj pojawił się kanał przeciwny o przepustowości rezydualnej równej 6.

Kanał (B,t) przestał istnieć w sieci rezydualnej, ponieważ osiągnął już swoją maksymalną przepustowość – 6 jednostek przepływu. Nie może on być dalej wykorzystywany do powiększania przepływu. Na jego miejscu mamy jednak kanał przeciwny z przepustowością rezydualną równą 6.

W nowej sieci rezydualnej szukamy kolejnej ścieżki rozszerzającej:

p = {s→A→C→t}, cf(p) = 3

Przepływ zwiększamy:

| f | = 6 + 3 = 9

i modyfikujemy przepustowości rezydualne krawędzi ścieżki rozszerzającej otrzymując nową sieć rezydualną. Znikają z niej kanały (s,A) i (A,C) – wykorzystały już swój potencjał zwiększania przepływu.

Szukamy kolejnej ścieżki rozszerzającej:

p = {s→D→E→t}, cf(p) = 6

W nowej sieci rezydualnej zniknął kanał (D,E).
Wciąż jednakże możemy znaleźć nową ścieżkę rozszerzającą:

p = {s→D→C→t}, cf(p) = 3

Przepływ zwiększamy:

| f | = 15 + 3 = 18.

Po zmodyfikowaniu sieci rezydualnej otrzymujemy nową sieć rezydualną. W tej sieci rezydualnej nie znajdziemy już żadnej nowej ścieżki rozszerzającej – ze źródła s nie wychodzi żaden kanał.

Otrzymaliśmy maksymalny przepływ. Z sieci rezydualnej można w prosty sposób przejść do sieci przepływowej wraz z rozkładem przepływów na poszczególne kanały. Wystarczy od przepustowości kanałów odjąć otrzymane przepustowości rezydualne – dla nieistniejących kanałów ich przepustowość rezydualna wynosi 0. W efekcie otrzymamy sieć przepływową z wyznaczonym maksymalnym przepływem sieciowym.

Zwróć uwagę, iż poprzez kanały (B,C) i (C,E) przepływ nie płynie. Są to kanały zbędne, które można zlikwidować.

 

Jeśli sieć przepływowa nie posiada kanałów skierowanych przeciwnie (u,v) i (v,u), to przepływy można bezpośrednio odczytać z kanałów przeciwnych (czyli tych, których nie ma w pierwotnej sieci) w sieci rezydualnej (zysk jest oczywisty - nie musimy zapamiętywać przepustowości kanałów sieci przepływowej). Na przykład przepływ przez kanał (D,E) wynosi f(D,E) = cf(E,D) = 6, a przez kanał (C,t) mamy przepływ f(C,t) = cf(t,C) = 6.

Algorytm Forda-Fulkersona jest właściwie szablonem postępowania. Aby go efektywnie zaimplementować, programista musi rozwiązać kilka problemów. Pierwszym z nich jest wybór sposobu reprezentowania sieci rezydualnej. Zasadniczo mamy dwie możliwości:

  1. Zastosowanie macierzy sąsiedztwa (ang. adjacency matrix) do reprezentacji sieci, przepustowości oraz przepływów. Sposób ten upraszcza obliczenia, jednakże zwiększa złożoność pamięciową do O(n2). Jeśli sieć przepływowa jest nieduża, można go z powodzeniem stosować. Przepustowości rezydualne kanałów nie musimy pamiętać - obliczamy je jako różnicę przepustowości kanału  i przepływu w tym kanale.
  2. Zastosowanie tablicy list sąsiedztwa (ang. adjacency list array), w której umieszczamy listy sąsiadów danego wierzchołka. Element takiej listy oprócz numeru wierzchołka w grafie sieci powinien zawierać informację o przepustowości kanału, przepływie oraz przynależności do sieci (kanały rezydualne mogą nie należeć do sieci przepływowej, stąd konieczność tego rozróżnienia). Sieć rezydualną można zrealizować w tym samym grafie dodając krawędzie przeciwne (o ile krawędź przeciwna już nie istnieje) i ustawiając dla nich przepustowość i przepływ 0 oraz brak przynależności do sieci pierwotnej (rezydualny kanał przeciwny). Sposób drugi pozwala zaoszczędzić na pamięci, jeśli sieć przepływowa posiada dużo węzłów o niewielkich stopniach. Okupione to zostaje jednakże wzrostem czasu przetwarzania oraz nieznaczną komplikacją algorytmu.

Drugim problemem w algorytmie Forda-Fulkersona jest sposób wyszukiwania ścieżek rozszerzających w sieci rezydualnej. Okazuje się, iż zastosowanie prostej metody DFS (ang. Deep First Search - przeszukiwanie w głąb) nie daje dobrych rezultatów, ponieważ DFS zwykle znajduje długie ścieżki. Tymczasem w algorytmie Forda-Fulkersona są preferowane ścieżki krótkie, czyli zawierające jak najmniejszą liczbę krawędzi grafu sieci przepływowej. Rozwiązaniem staje się zastosowanie metody BFS (ang. Breadth First Search - przeszukiwanie w szerz), która zawsze znajduje najkrótsze ścieżki ze względu na ilość krawędzi.

 

Algorytm Edmondsa-Karpa

Algorytm Forda-Fulkersona wykorzystujący metodę BFS do wyszukiwania ścieżek rozszerzających w sieci rezydualnej nosi nazwę algorytmu Edmondsa-Karpa.

 

Algorytm Edmondsa-Karpa wyszukujący maksymalny przepływ - wersja z macierzami sąsiedztwa

Wejście
n  –  liczba wierzchołków w grafie, n symbol C
C  –  macierz n x n przepustowości kanałów
s  –  numer wierzchołka będącego źródłem sieci, s symbol C
t  –  numer wierzchołka będącego ujściem sieci, t symbol C
Wyjście
F  –  macierz n x n przepływów netto
fmax  –  wartość maksymalnego przepływu sieciowego
Elementy pomocnicze:
Q  –  kolejka przechowująca wierzchołki dla metody BFS
P  –  tablica n elementowa przechowująca ścieżki (poprzedniki) wyszukiwane przez BFS
CFP  –  tablica n elementowa przechowująca wartości cf(p) dla ścieżki kończącej się w danym węźle sieci
cp  –  przechowuje wartość przepustowości rezydualnej
x,y  –  przechowują numery wierzchołków połączonych krawędzią, x,y symbol C
Lista kroków:
K01: fmax ← 0 ; zerujemy wartość przepływu sieciowego
K02: Wyzeruj macierz F  
K03:     Dla y = 0,1,...,n - 1, wykonuj:  P[y] ← -1  
K04:     P[s] ← -2 ; to zapobiegnie wybieraniu źródła przez BFS
K05:     CFP[s] ← ∞ ; w CFP przechowujemy przepustowość rezydualną ścieżki
K06:     Dopóki Q.empty() = false, wykonuj Q.pop() ; zerujemy kolejkę
K07:     Q.push(s) ; w kolejce umieszczamy numer źródła
K08:     Dopóki Q.empty() = false, wykonuj K09...K16  
K09:         x = Q.front();  Q.pop() ; pobieramy numer wierzchołka z kolejki
K10:         Dla y = 0,1,...,n - 1, wykonuj K11...K16 ; rozpoczynamy BFS
K11:             cpC[x][y] - F[x][y] ; wyznaczamy przepustowość rezydualną kanału (x,y)
K12:             Jeśli (cp = 0) (P[y] ≠ -1), to następny obieg pętli K10 ; omijamy przy braku krawędzi lub odwiedzonym sąsiedzie
K13:             P[y] ← x ; zapamiętujemy poprzednik na ścieżce
K14:             CPF[y] ← min(CPF[x],cp) ; obliczamy przepustowość rezydualną do węzła y
K15:             Jeśli y = t, to idź do K18 ; ścieżka rozszerzająca znaleziona!
K16:             Q.push(y)  
K17:     Zakończ ; brak ścieżki, kończymy
K18:     fmaxfmax + CFP[t] ; zwiększamy przepływ sieciowy
K19:     Dopóki ys, wykonuj K20...K23 ; cofamy się po ścieżce rozszerzającej od ujścia t do źródła s
K20:         xP[y] ; (x,y) jest krawędzią ścieżki rozszerzającej
K21:         F[x,y] ← F[x,y] + CFP[t] ; w kierunku zgodnym ze ścieżką zwiększamy przepływ
K22:         F[y,x] ← F[y,x] - CFP[t] ; w kierunku przeciwnym zmniejszamy przepływ
K23:         yx ; przechodzimy do następnej krawędzi ścieżki
K24: Idź do K03  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję sieci przepływowej o następującej postaci:

 

Pierwsze dwie liczby określają kolejno liczbę wierzchołków n oraz liczbę krawędzi m sieci przepływowej. Dalej występuje m trójek liczb określających krawędzie sieci. Każda trójka definiuje kolejno: wierzchołek startowy, wierzchołek końcowy oraz przepustowość kanału. W naszym przykładzie przepustowości są liczbami całkowitymi. Na samym końcu danych występują dodatkowo dwie liczby, które definiują źródło i ujście sieci.

 

Po odczytaniu definicji sieci program wyznacza maksymalny przepływ oraz przepływy netto w poszczególnych kanałach sieci.

Przykładowe dane dla programu:

  7 11
0 1 7 0 3 3
1 3 4 1 4 6
2 0 9 2 5 9
3 4 9 3 6 2
5 3 3 5 6 6
6 4 8
2 4

 

Lazarus
// Maksymalny przepływ - algorytm Edmondsa-Karpa
// Data: 08.08.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------

program maxflow;

// Definicja typu elementów listy
//-------------------------------
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.data;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(v : integer);
var
  p : PslistEl;
begin
  new(p);
  p^.next := nil;
  p^.data := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(p);
  end;
end;

//---------------
// Program główny
//---------------

var
  Q : queue;                      // Kolejka
  C : array of array of integer;  // Macierz przepustowości
  F : array of array of integer;  // Macierz przepływów netto
  P : array of integer;           // Tablica poprzedników
  CFP : array of integer;         // Tablica przepustowości rezydualnych
  n,m,s,t,fmax,cp,x,y,i,j : integer;  // Zmienne proste algorytmu
  esc : boolean;                  // Do wychodzenia z zagnieżdżonych pętli

begin
  Q.init;                         // Inicjujemy kolejkę

  // Ze standardowego wejścia odczytujemy
  // n - liczbę wierzchołków w grafie sieci
  // m - liczbę krawędzi

  read(n,m);

  // Tworzymy dynamicznie macierze:
  // C - przepustowości krawędzi
  // F - przepływy w krawędziach

  SetLength(C,n); SetLength(F,n);
  for i := 0 to n - 1 do
  begin
    SetLength(C[i],n);
    SetLength(F[i],n);
  end;

  // Tworzymy dynamicznie tablice:
  // P   - poprzedniki na ścieżkach tworzonych przez BFS
  // CFP - przepustowość ścieżek

  SetLength(P,n);
  SetLength(CFP,n);

  // Zerujemy macierze przepustowości i przepływów

  for i := 0 to n - 1 do
    for j := 0 to n - 1 do
    begin
      C[i][j] := 0;
      F[i][j] := 0;
    end;

  // Ze standardowego wejścia odczytujemy definicje krawędzi.
  // Każda definicja składa się z trzech liczb
  // x,y - wierzchołki grafu połączone krawędzią
  // cp  - przepustowość krawędzi
  // Odczytane dane zapamiętujemy: C[x][y] = cp

  for i := 1 to m do
  begin
    read(x,y,cp);
    C[x][y] := cp;
  end;

  // Na koniec odczytujemy numer wierzchołka źródła s
  // oraz numer wierzchołka ujścia t

  read(s,t);

  //**************************************************
  //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
  //**************************************************

  // Rozpoczynamy od maksymalnego przepływu równego zero

  fmax := 0;

  // W pętli szukamy ścieżek rozszerzających dotąd,
  // dopóki istnieją w sieci rezydualnej. Każda znaleziona
  // ścieżka zwiększa przepływ wzdłuż zawartych w niej
  // krawędzi grafu sieci przepływowej

  while true do
  begin

    // Na początku pętli zerujemy tablicę poprzedników P

    for i := 0 to n - 1 do P[i] := -1;

    // źródło nie posiada poprzednika. Wpisujemy tutaj -2,
    // aby BFS nie wybierało źródła

    P[s] := -2;

    // Do CFP[s] wpisujemy największą liczbę całkowitą

    CFP[s] := MAXINT;

    // Zerujemy kolejkę i umieszczamy w niej źródło s

    while not Q.empty do Q.pop;
    Q.push(s);

    // Zmienna esc umożliwia odpowiednie wychodzenie z
    // dwóch zagnieżdżonych pętli - zamiast polecenie goto.

    esc := false;

    // Rozpoczynamy pętlę wyszukującą ścieżki BFS. Pętla kończy
    // się w przypadku braku dalszych wierzchołków w kolejce

    while not Q.empty do
    begin

      // Z początku kolejki pobieramy element i usuwamy go z kolejki

      x := Q.front; Q.pop;

      // Sprawdzamy wszystkich sąsiadów wierzchołka x przeglądając
      // wiersz macierzy C

      for y := 0 to n - 1 do
      begin

        // Dla sąsiada y wyznaczamy przepustowość rezydualną
        // krawędzi x->y. Jeśli krawędź nie istnieje w sieci,
        // to otrzymamy w cp wynik zero

        cp := C[x][y] - F[x][y];

        // Sprawdzamy, czy krawędź istnieje oraz czy wierzchołek
        // y nie był już wcześniej wybrany przez BFS. W takim
        // przypadku P[y] ma wartość różną od -1.

        if (cp <> 0) and (P[y] = -1) then
        begin

          // W P[y] zapamiętujemy, iż poprzednikiem y jest x

          P[y] := x;

          // Dla wierzchołka y obliczamy dotychczasową przepustowość
          // rezydualną ścieżki. Jest to mniejsza wartość z przepustowości
          // ścieżki dla poprzednika x i bieżącej przepustowości
          // rezydualnej krawędzi x->y.

          if CFP[x] > cp then CFP[y] := cp else CFP[y] := CFP[x];

          // Jeśli osiągnęliśmy ujście, to ścieżka jest kompletna

          if y = t then
          begin

            // Zwiększamy przepływ maksymalny o przepustowość rezydualną
            // ścieżki - wykorzystujemy tablicę CFP

            inc(fmax,CFP[t]);

            // Idziemy wstecz po ścieżce zwiększając przepływy
            // wzdłuż jej krawędzi w kierunku zgodnym ze ścieżką
            // oraz zmniejszając przepływy w kierunku przeciwnym

            i := y;
            while i <> s do
            begin
              x := P[i];
              inc(F[x][i],CFP[t]);
              dec(F[i][x],CFP[t]);
              i := x;
            end;

            // Ustawiamy esc na true, co spowoduje wyjście z obu pętli

            esc := true; break;

          end;

          // Jeśli wierzchołek y nie jest ujściem t, to dopisujemy
          // go na końcu kolejki Q i kontynuujemy pętlę BFS

          Q.push(y);

        end;
      end;

      // Tutaj wychodzimy z pętli while, jeśli
      // została znaleziona ścieżka rozszerzająca

       if esc then break;

    end;

    // Jeśli nie znaleziono ścieżki rozszerzającej, to esc = false
    // i w tym miejscu nastąpi wyjście z głównej pętli while

    if not esc then break;

  end;

  // Prezentujemy wyniki obliczeń. Najpierw wypisujemy
  // wartość maksymalnego przepływu

  writeln;
  writeln('fmax = ',fmax);
  writeln;

  // Następnie wypisujemy przepływy netto wzdłuż krawędzi

  for x := 0 to n - 1 do
    for y := 0 to n - 1 do
      if C[x][y] <> 0 then writeln(x,' -> ',y,' ',F[x][y],':',C[x][y]);

  writeln;

  // Usuwamy zmienne dynamiczne

  for i := 0 to n - 1 do
  begin
    SetLength(C[i],0);
    SetLength(F[i],0);
  end;

  SetLength(C,0);
  SetLength(F,0);
  SetLength(P,0);
  SetLength(CFP,0);

  Q.destroy;

end.
Code::Blocks
// Maksymalny przepływ - algorytm Edmondsa-Karpa
// Data: 08.08.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu elementów listy
//-------------------------------
struct slistEl
{
  slistEl * next;
  int data;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      // konstruktor
    ~queue();     // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(head) return head->data;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->data = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  queue Q;                        // Kolejka
  int ** C;                       // Macierz przepustowości
  int ** F;                       // Macierz przepływów netto
  int * P;                        // Tablica poprzedników
  int * CFP;                      // Tablica przepustowości rezydualnych
  int n,m,s,t,fmax,cp,x,y,i,j;    // Zmienne proste algorytmu
  bool esc;                       // Do wychodzenia z zagnieżdżonych pętli

  // Ze standardowego wejścia odczytujemy
  // n - liczbę wierzchołków w grafie sieci
  // m - liczbę krawędzi

  cin >> n >> m;

  // Tworzymy dynamicznie macierze:
  // C - przepustowości krawędzi
  // F - przepływy w krawędziach

  C = new int * [n];
  F = new int * [n];
  for(i = 0; i < n; i++)
  {
    C[i] = new int [n];
    F[i] = new int [n];
  }

  // Tworzymy dynamicznie tablice:
  // P   - poprzedniki na ścieżkach tworzonych przez BFS
  // CFP - przepustowość ścieżek

  P = new int [n];
  CFP = new int [n];

  // Zerujemy macierze przepustowości i przepływów

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++) C[i][j] = F[i][j] = 0;

  // Ze standardowego wejścia odczytujemy definicje krawędzi.
  // Każda definicja składa się z trzech liczb
  // x,y - wierzchołki grafu połączone krawędzią
  // cp  - przepustowość krawędzi
  // Odczytane dane zapamiętujemy: C[x][y] = cp

  for(i = 0; i < m; i++)
  {
    cin >> x >> y >> cp;
    C[x][y] = cp;
  }

  // Na koniec odczytujemy numer wierzchołka źródła s
  // oraz numer wierzchołka ujścia t

  cin >> s >> t;

  //**************************************************
  //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
  //**************************************************

  // Rozpoczynamy od maksymalnego przepływu równego zero

  fmax = 0;

  // W pętli szukamy ścieżek rozszerzających dotąd,
  // dopóki istnieją w sieci rezydualnej. Każda znaleziona
  // ścieżka zwiększa przepływ wzdłuż zawartych w niej
  // krawędzi grafu sieci przepływowej

  while(true)
  {

    // Na początku pętli zerujemy tablicę poprzedników P

    for(i = 0; i < n; i++) P[i] = -1;

    // źródło nie posiada poprzednika. Wpisujemy tutaj -2,
    // aby BFS nie wybierało źródła

    P[s] = -2;

    // Do CFP[s] wpisujemy największą liczbę całkowitą

    CFP[s] = MAXINT;

    // Zerujemy kolejkę i umieszczamy w niej źródło s

    while(!Q.empty()) Q.pop();
    Q.push(s);

    // Zmienna esc umożliwia odpowiednie wychodzenie z
    // dwóch zagnieżdżonych pętli - zamiast polecenie goto.

    esc = false;

    // Rozpoczynamy pętlę wyszukującą ścieżki BFS. Pętla kończy
    // się w przypadku braku dalszych wierzchołków w kolejce

    while(!Q.empty())
    {

      // Z początku kolejki pobieramy element i usuwamy go z kolejki

      x = Q.front(); Q.pop();

      // Sprawdzamy wszystkich sąsiadów wierzchołka x przeglądając
      // wiersz macierzy C

      for(y = 0; y < n; y++)
      {

        // Dla sąsiada y wyznaczamy przepustowość rezydualną
        // krawędzi x->y. Jeśli krawędź nie istnieje w sieci,
        // to otrzymamy w cp wynik zero

        cp = C[x][y] - F[x][y];

        // Sprawdzamy, czy krawędź istnieje oraz czy wierzchołek
        // y nie był już wcześniej wybrany przez BFS. W takim
        // przypadku P[y] ma wartość różną od -1.

        if(cp && (P[y] == -1))
        {

          // W P[y] zapamiętujemy, iż poprzednikiem y jest x

          P[y] = x;

          // Dla wierzchołka y obliczamy dotychczasową przepustowość
          // rezydualną ścieżki. Jest to mniejsza wartość z przepustowości
          // ścieżki dla poprzednika x i bieżącej przepustowości
          // rezydualnej krawędzi x->y.

          CFP[y] = CFP[x] > cp ? cp : CFP[x];

          // Jeśli osiągnęliśmy ujście, to ścieżka jest kompletna

          if(y == t)
          {

            // Zwiększamy przepływ maksymalny o przepustowość rezydualną
            // ścieżki - wykorzystujemy tablicę CFP

            fmax += CFP[t];

            // Idziemy wstecz po ścieżce zwiększając przepływy
            // wzdłuż jej krawędzi w kierunku zgodnym ze ścieżką
            // oraz zmniejszając przepływy w kierunku przeciwnym

            i = y;
            while(i != s)
            {
              x = P[i];
              F[x][i] += CFP[t];
              F[i][x] -= CFP[t];
              i = x;
            }

            // Ustawiamy esc na true, co spowoduje wyjście z obu pętli

            esc = true; break;
          }

          // Jeśli wierzchołek y nie jest ujściem t, to dopisujemy
          // go na końcu kolejki Q i kontynuujemy pętlę BFS

          Q.push(y);
        }
      }

      // Tutaj wychodzimy z pętli while, jeśli
      // została znaleziona ścieżka rozszerzająca

       if(esc) break;
    }

    // Jeśli nie znaleziono ścieżki rozszerzającej, to esc = false
    // i w tym miejscu nastąpi wyjście z głównej pętli while

    if(!esc) break;
  }

  // Prezentujemy wyniki obliczeń. Najpierw wypisujemy
  // wartość maksymalnego przepływu

  cout << endl << "fmax = " << fmax << endl << endl;

  // Następnie wypisujemy przepływy netto wzdłuż krawędzi

  for(x = 0; x < n; x++)
    for(y = 0; y < n; y++)
      if(C[x][y]) cout << x << " -> " << y << " " << F[x][y] << ":" << C[x][y] << endl;

  cout << endl;

  // Usuwamy zmienne dynamiczne

  for(i = 0; i < n; i++)
  {
    delete [] C[i];
    delete [] F[i];
  }

  delete [] C;
  delete [] F;
  delete [] P;
  delete [] CFP;

  return 0;
}
Free Basic
' Maksymalny przepływ - algorytm Edmondsa-Karpa
' Data: 08.08.2014
' (C)2014 mgr Jerzy Wałaszek
'----------------------------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type slistEl
  next As slistEl Ptr
  data As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->data
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->data = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

Dim As queue Q                    ' Kolejka
Dim As Integer Ptr Ptr C          ' Macierz przepustowości
Dim As Integer Ptr Ptr F          ' Macierz przepływów netto
Dim As Integer Ptr P              ' Tablica poprzedników
Dim As Integer Ptr CFP            ' Tablica przepustowości rezydualnych
Dim As Integer n,m,s,t,fmax,cp,x,y,i,j ' Zmienne proste algorytmu
Dim As Byte esc                   ' Do wychodzenia z zagnieżdżonych pętli

Open Cons For Input As #1

' Ze standardowego wejścia odczytujemy
' n - liczbę wierzchołków w grafie sieci
' m - liczbę krawędzi

Input #1,n,m

' Tworzymy dynamicznie macierze:
' C - przepustowości krawędzi
' F - przepływy w krawędziach

C = New Integer Ptr [n]
F = New Integer Ptr [n]
For i = 0 To n - 1
  C[i] = New Integer [n]
  F[i] = New Integer [n]
Next

' Tworzymy dynamicznie tablice:
' P   - poprzedniki na ścieżkach tworzonych przez BFS
' CFP - przepustowość ścieżek

P = New Integer [n]
CFP = New Integer [n]

' Zerujemy macierze przepustowości i przepływów

For i = 0 To n - 1
  For j = 0 To n - 1
  	 C[i][j] = 0
  	 F[i][j] = 0
  Next
Next

' Ze standardowego wejścia odczytujemy definicje krawędzi.
' Każda definicja składa się z trzech liczb
' x,y - wierzchołki grafu połączone krawędzią
' cp  - przepustowość krawędzi
' Odczytane dane zapamiętujemy: C[x][y] = cp

For i = 1 To m
  Input #1,x,y,cp
  C[x][y] = cp
Next

' Na koniec odczytujemy numer wierzchołka źródła s
' oraz numer wierzchołka ujścia t

Input #1,s,t

Close #1

'**************************************************
'** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
'**************************************************

' Rozpoczynamy od maksymalnego przepływu równego zero

fmax = 0

' W pętli szukamy ścieżek rozszerzających dotąd,
' dopóki istnieją w sieci rezydualnej. Każda znaleziona
' ścieżka zwiększa przepływ wzdłuż zawartych w niej
' krawędzi grafu sieci przepływowej

While 1

  ' Na początku pętli zerujemy tablicę poprzedników P

  For i = 0 To n - 1
  	 P[i] = -1
  Next

  ' źródło nie posiada poprzednika. Wpisujemy tutaj -2,
  ' aby BFS nie wybierało źródła

  P[s] = -2

  ' Do CFP[s] wpisujemy największą liczbę całkowitą

  CFP[s] = MAXINT

  ' Zerujemy kolejkę i umieszczamy w niej źródło s

  While Q.empty() = 0
  	 Q.pop()
  Wend
  Q.push(s)
  
  ' Zmienna esc umożliwia odpowiednie wychodzenie z
  ' dwóch zagnieżdżonych pętli - zamiast polecenie goto.

  esc = 0

  ' Rozpoczynamy pętlę wyszukującą ścieżki BFS. Pętla kończy
  ' się w przypadku braku dalszych wierzchołków w kolejce

  While Q.empty() = 0

    ' Z początku kolejki pobieramy element i usuwamy go z kolejki

    x = Q.front()
    Q.pop()

    ' Sprawdzamy wszystkich sąsiadów wierzchołka x przeglądając
    ' wiersz macierzy C

    For y = 0 To n - 1

      ' Dla sąsiada y wyznaczamy przepustowość rezydualną
      ' krawędzi x->y. Jeśli krawędź nie istnieje w sieci,
      ' to otrzymamy w cp wynik zero

      cp = C[x][y] - F[x][y]

      ' Sprawdzamy, czy krawędź istnieje oraz czy wierzchołek
      ' y nie był już wcześniej wybrany przez BFS. W takim
      ' przypadku P[y] ma wartość różną od -1.

      If cp <> 0 AndAlso P[y] = -1 Then

        ' W P[y] zapamiętujemy, iż poprzednikiem y jest x

        P[y] = x

        ' Dla wierzchołka y obliczamy dotychczasową przepustowość
        ' rezydualną ścieżki. Jest to mniejsza wartość z przepustowości
        ' ścieżki dla poprzednika x i bieżącej przepustowości
        ' rezydualnej krawędzi x->y.

        If CFP[x] > cp Then
        	 CFP[y] = cp
        Else
        	 CFP[y] = CFP[x]
        EndIf

        ' Jeśli osiągnęliśmy ujście, to ścieżka jest kompletna

        If y = t Then

          ' Zwiększamy przepływ maksymalny o przepustowość rezydualną
          ' ścieżki - wykorzystujemy tablicę CFP

          fmax += CFP[t]

          ' Idziemy wstecz po ścieżce zwiększając przepływy
          ' wzdłuż jej krawędzi w kierunku zgodnym ze ścieżką
          ' oraz zmniejszając przepływy w kierunku przeciwnym

          i = y
          While i <> s
            x = P[i]
            F[x][i] += CFP[t]
            F[i][x] -= CFP[t]
            i = x
          Wend

          ' Ustawiamy esc na true, co spowoduje wyjście z obu pętli

          esc = 1
          Exit For
        EndIf

        ' Jeśli wierzchołek y nie jest ujściem t, to dopisujemy
        ' go na końcu kolejki Q i kontynuujemy pętlę BFS

        Q.push(y)
      EndIf
    Next

    ' Tutaj wychodzimy z pętli while, jeśli
    ' została znaleziona ścieżka rozszerzająca

    If esc = 1 Then Exit While
  Wend

  ' Jeśli nie znaleziono ścieżki rozszerzającej, to esc = false
  ' i w tym miejscu nastąpi wyjście z głównej pętli while

  If esc = 0 Then Exit While
Wend

' Prezentujemy wyniki obliczeń. Najpierw wypisujemy
' wartość maksymalnego przepływu

Print
Print "fmax =";fmax
Print

' Następnie wypisujemy przepływy netto wzdłuż krawędzi

For x = 0 To n - 1
  For y = 0 To n - 1
    If C[x][y] <> 0 Then Print Using "& -> & &:&";x;y;F[x][y];C[x][y]
  Next
Next

Print

' Usuwamy zmienne dynamiczne

for i = 0 To n - 1
  Delete [] C[i]
  Delete [] F[i]
Next

Delete [] C
Delete [] F
Delete [] P
Delete [] CFP

End
Wynik
7 11
0 1 7 0 3 3
1 3 4 1 4 6
2 0 9 2 5 9
3 4 9 3 6 2
5 3 3 5 6 6
6 4 8
2 4

fmax = 18

0 -> 1 6:7
0 -> 3 3:3
1 -> 3 0:4
1 -> 4 6:6
2 -> 0 9:9
2 -> 5 9:9
3 -> 4 6:9
3 -> 6 0:2
5 -> 3 3:3
5 -> 6 6:6
6 -> 4 6:8

 

Algorytm Edmondsa-Karpa wyszukujący maksymalny przepływ - wersja z listami sąsiedztwa

Wejście
n  –  liczba wierzchołków w grafie, n symbol C
L  –  tablica list sąsiedztwa. Każdy element listy zawiera następujące pola:
next – adres następnego elementu listy
v  – numer wierzchołka końcowego
c – przepustowość kanału
f – przepływ w kanale
s  –  numer wierzchołka będącego źródłem, s symbol C
t  –  numer wierzchołka będącego ujściem, t symbol C
Wyjście
L  –  tablica list sąsiedztwa z obliczonymi przepływami netto
fmax  –  wartość maksymalnego przepływu sieciowego
Elementy pomocnicze:
Q  –  kolejka przechowująca wierzchołki dla metody BFS
P  –  tablica n elementowa przechowująca ścieżki (poprzedniki) wyszukiwane przez BFS
CFP  –  tablica n elementowa przechowująca wartości cf(p) dla ścieżki kończącej się w danym węźle sieci
cp  –  przechowuje wartość przepustowości rezydualnej
u,v  –  numery wierzchołków,  u,v symbol C
x,z  –  wskaźniki elementów list sąsiedztwa
Lista kroków:
K01: fmax ← 0 ; zerujemy wartość przepływu sieciowego
K02: Wyzeruj wszystkie przepływy w L  
K03: Dla u = 1,2,...,n wykonuj K04...K08 ; tworzymy strukturę sieci rezydualnej
K04:     Dla każdego sąsiada x wierzchołka u wykonuj K05...K08 ; w grafie sieci przepływowej
K05:         Jeśli istnieje z na liście L[(xv)] taki, że (xv) = u, to następny obieg pętli K04 ; dodając krawędzie przeciwne tam, gdzie
K06:         Utwórz nowy element listy i przypisz jego adres do z ; jest to konieczne
K07:         (zv) ← u;  (zc) ← 0;  (zf) ← 0  
K08:         Dodaj z do listy sąsiedztwa L[(xv)]  
K09: W elementach tablicy P umieść wartość -1 ; zerujemy poprzedniki na ścieżce rozszerzającej
K10: P[s] ← -2 ; to zapobiegnie wybieraniu źródła przez BFS
K11: CFP[s] ← ∞ ; w cfp[ ] przechowujemy przepustowość rezydualną ścieżki
K12: Wyczyść kolejkę Q  
K13: Q.push(s) ; w kolejce umieszczamy źródło s
K14: Dopóki ¬ Q.empty() , wykonuj K15...K22  
K15:     uQ.front(); Q.pop() ; do u pobieramy początek kolejki
K16:     Dla każdego sąsiada x wierzchołka u wykonuj K17...K22 ; rozpoczynamy BFS
K17:         cp ← (xc) - (xf) ; wyznaczamy przepustowość rezydualną kanału (x,y.v)
K18:         Jeśli (cp = 0) (P[(xv)] ≠ -1), wykonaj następny obieg K16 ; omijamy przy braku krawędzi lub odwiedzonym sąsiedzie
K19:         P[(xv)] ← u ; zapamiętujemy poprzednik na ścieżce
K20:         CFP[(xv)] ← min(CFP[u], cp) ; obliczamy przepustowość rezydualną do węzła x->v
K21:         Jeśli (xv) = t, to idź do K24 ; ścieżka rozszerzająca znaleziona!
K22:         Q.push(xv)  
K23: Zakończ ; brak ścieżki, kończymy algorytm
K24: fmaxfmax + CFP[t] ; zwiększamy przepływ sieciowy
K25: vt  
K26: Dopóki vs: wykonuj K27...K30 ; cofamy się po ścieżce rozszerzającej od t do s
K27:     uP[v] ; (u,v) jest krawędzią ścieżki rozszerzającej
K28:     Znajdź na liście L[u] element z taki, że (zv) = v.
    Dla tego elementu wykonaj: (zf) ← (zf) + CFP[t]
; w kierunku zgodnym ze ścieżką zwiększamy przepływ
K29:     Znajdź na liście L[v] element z taki, że (zv) = u.
    Dla tego elementu wykonaj: (zf) ← (zf) - CFP[t]
; w kierunku przeciwnym zmniejszamy przepływ
K30:     vu ; przechodzimy do następnej krawędzi ścieżki
K31: Idź do K09  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję sieci przepływowej o następującej postaci:

 

Pierwsze dwie liczby określają kolejno liczbę wierzchołków n oraz liczbę krawędzi m sieci przepływowej. Dalej występuje m trójek liczb określających krawędzie sieci. Każda trójka definiuje kolejno: wierzchołek startowy, wierzchołek końcowy oraz przepustowość kanału. W naszym przykładzie przepustowości są liczbami całkowitymi. Na samym końcu danych występują dodatkowo dwie liczby, które definiują źródło i ujście sieci.

 

Po odczytaniu definicji sieci program wyznacza maksymalny przepływ oraz przepływy netto w poszczególnych kanałach sieci.

Przykładowe dane dla programu:

  7 11
0 1 7 0 3 3
1 3 4 1 4 6
2 0 9 2 5 9
3 4 9 3 6 2
5 3 3 5 6 6
6 4 8
2 4

 

Lazarus
// Maksymalny przepływ - algorytm Edmondsa-Karpa
// Data: 24.08.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------

program maxflow;

// Definicja typu elementów listy
//-------------------------------
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    v,c,f : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
queue = object
  private
    head : PslistEl;
    tail : PslistEl;

  public
    constructor init;
    destructor  destroy;
    function    empty : boolean;
    function    front : integer;
    procedure   push(x : integer);
    procedure   pop;
end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(x : integer);
  var
    p : PslistEl;
begin
  new(p);
  p^.next := nil;
  p^.v    := x;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
  var
    p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(p);
  end;
end;

//---------------
// Program główny
//---------------

var
  m,n      : integer;             // Liczba krawędzi i wierzchołków w grafie
  L        : array of PslistEl;   // Tablica list sąsiedztwa
  s,t      : integer;             // Numer wierzchołka źródła s i ujscia t
  fmax     : integer;             // Maksymalny przepływ sieciowy
  Q        : queue;               // Kolejka
  P        : array of integer;    // Tablica poprzedników
  CFP      : array of integer;    // Tablica przepustowości rezydualnych dla ścieżek
  i,cp,u,v : integer;             // Zmienne pomocnicze
  x,z      : PslistEl;            // Wskaźniki elementów listy sąsiedztwa
  test     : boolean;

begin

  Q.init;

  // Najpierw odczytujemy liczbę wierzchołków i krawędzi grafu

  read(n,m);

  // Tworzymy i inicjujemy struktury dynamiczne

  SetLength(L,n);                 // Tablica wskaźników list
  for i := 0 to n - 1 do
    L[i] := nil;                  // Tablicę wypełniamy pustymi listami

  SetLength(P,n);
  SetLength(CFP,n);

  // Teraz wczytujemy definicje poszczególnych krawędzi grafu.
  // Każda krawędź jest zdefiniowana przez trzy liczby u, v i cp:
  // u  - wierzchołek początkowy krawędzi
  // v  - wierzchołek końcowy krawędzi
  // cp - przepustowość krawędzi

  for i := 1 to m do
  begin
    // Najpierw odczytujemy te trzy liczby

    read(u,v,cp);

    // Tworzymy nowy element listy

    new(x);

    // Wypełniamy jego pola danych

    x^.v := v;
    x^.c := cp;
    x^.f := 0;                     // Zerujemy przepływ

    // Element dołączamy do listy sąsiadów wierzchołka u

    x^.next := L[u];
    L[u] := x;
  end;

  // Na koniec odczytujemy numery wierzchołków źródła i ujścia

  read(s,t);

  //**************************************************
  //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
  //**************************************************

  // Zerujemy wartość maksymalnego przepływu sieciowego

  fmax := 0;

  // Tworzymy w grafie strukturę sieci rezydualnej

  for u := 0 to n - 1 do
  begin
    x := L[u];
    while x <> nil do
    begin
      // Sprawdzamy, czy na liście sąsiadów x jest wierzchołek u.
      // Jeśli tak, to krawędź zwrotna istnieje i nie ma potrzeby
      // jej tworzenia.

      test := false;              // Zakładamy brak krawędzi zwrotnej
      z := L[x^.v];
      while z <> nil do
      begin
        if z^.v = u then
        begin
          test := true; break;
        end;
        z := z^.next;
      end;

      if not test then            // Jeśli brak krawędzi, tworzymy ją
      begin
        new(z);
        z^.v := u;
        z^.c := 0;
        z^.f := 0;
        z^.next := L[x^.v];
        L[x^.v] := z;
      end;
      x := x^.next;
    end;
  end;

  // Sieć rezydualna została utworzona. Teraz zajmiemy się wyznaczeniem
  // maksymalnych przepływów w sieci.

  while true do
  begin
    for i := 0 to n - 1 do
      P[i] := -1;                 // Zerujemy tablicę poprzedników

    CFP[s] := MAXINT;             // Przepustowość źródła jest nieskończona

    while not Q.empty do Q.pop;   // Zerujemy kolejkę

    Q.push(s);                    // W kolejce umieszczamy źródło s

    // Szukamy ścieżki w sieci rezudualnej od źródła s do ujścia t

    while not Q.empty do
    begin
      test := false;              // Zakładamy brak takiej ścieżki
      u := Q.front; Q.pop;        // Pobieramy wierzchołek z kolejki

      // Przeglądamy listę sąsiadów wierzchołka u

      x := L[u];
      while x <> nil do
      begin
        // Wyznaczamy przepustowość rezydualną kanału

        cp := x^.c - x^.f;

        // Przetwarzamy tylko istniejące i nieodwiedzone jeszcze krawędzie

        if (cp <> 0) and (P[x^.v] = -1) then
        begin
          // Zapamiętujemy poprzednik na ścieżce

          P[x^.v] := u;

          // Obliczamy przepustowość rezydualną do węzła x^.v

          if cp < CFP[u] then CFP[x^.v] := cp else CFP[x^.v] := CFP[u];

          // Sprawdzamy, czy ścieżka sięga do ujścia

          if x^.v = t then
          begin
            test := true;         // Sygnalizujemy znalezioną ścieżkę
            break;                // Wychodzimy z pętli for
          end
          else Q.push(x^.v);      // Inaczej umieszczamy w kolejce wierzchołek x^.v
        end;

        x := x^.next;
      end;

      if test then break;         // Jeśli jest ścieżka, wychodzimy z pętli while
    end;

    if not test then break;       // Jeśli brak ścieżki, kończymy algorytm

    // Zwiększamy przepływ sieciowy

    inc(fmax,CFP[t]);

    // Cofamy się po ścieżce od ujścia t do źródła s

    v := t;
    while v <> s do
    begin
      u := P[v];                  // u jest poprzednikiem v na ścieżce

      // Szukamy na liście sąsiadów u krawędzi prowadzącej do v.

      z := L[u];
      while z <> nil do
      begin
        if z^.v = v then
        begin
          inc(z^.f,CFP[t]);       // W kierunku zgodnym ze ścieżką zwiększamy przepływ
          break;
        end;
        z := z^.next;
      end;

      // Szukamy na liście sąsiadów v krawędzi prowadzącej do u.

      z := L[v];
      while z <> nil do
      begin
        if z^.v = u then
        begin
          dec(z^.f,CFP[t]);       // W kierunku przeciwnym do ścieżki zmnejszamy przepływ
          break;
        end;
        z := z^.next;
      end;

      v := u;
    end;
  end;

  // Prezentujemy wyniki obliczeń. Najpierw wypisujemy
  // wartość maksymalnego przepływu

  writeln;
  writeln('fmax = ',fmax);
  writeln;

  // Następnie wypisujemy znalezione przez algorytm przepływy w
  // kanałach pierwotnej sieci przepływowej. Kanały rozpoznajemy
  // po niezerowej wartości ich przepustowości.

  for i := 0 to n - 1 do
  begin
    z := L[i];
    while z <> nil do
    begin
      if z^.c <> 0 then writeln(i,' -> ',z^.v,' ',z^.f,':',z^.c);
      z := z^.next;
    end;
  end;
  writeln;

  // Koniec, usuwamy struktury dynamiczne

  for i := 0 to n - 1 do
  begin
    x := L[i];
    while x <> nil do
    begin
      z := x;
      x := x^.next;
      dispose(z);
    end;
  end;

  SetLength(L,0);
  SetLength(P,0);
  SetLength(CFP,0);
  Q.destroy;

end.
Code::Blocks
// Maksymalny przepływ - algorytm Edmondsa-Karpa
// Data: 24.08.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu elementów listy
//-------------------------------
struct slistEl
{
  slistEl * next;
  int v,c,f;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      // konstruktor
    ~queue();     // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(head) return head->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->v = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  int m,n;                        // Liczba krawędzi i wierzchołków w grafie
  slistEl ** L;                   // Tablica list sąsiedztwa
  int s,t;                        // Numer wierzchołka źródła s i ujscia t
  int fmax;                       // Maksymalny przepływ sieciowy
  queue Q;                        // Kolejka
  int *P;                         // Tablica poprzedników
  int *CFP;                       // Tablica przepustowości rezydualnych dla ścieżek
  int i,cp,u,v;                   // Zmienne pomocnicze
  slistEl *x, *z;                 // Wskaźniki elementów listy sąsiedztwa
  bool test;

  // Najpierw odczytujemy liczbę wierzchołków i krawędzi grafu

  cin >> n >> m;

  // Tworzymy i inicjujemy struktury dynamiczne

  L = new slistEl * [n];          // Tablica wskaźników list
  for(i = 0; i < n; i++)
    L[i] = NULL;                  // Tablicę wypełniamy pustymi listami

  P   = new int [n];
  CFP = new int [n];

  // Teraz wczytujemy definicje poszczególnych krawędzi grafu.
  // Każda krawędź jest zdefiniowana przez trzy liczby u, v i cp:
  // u  - wierzchołek początkowy krawędzi
  // v  - wierzchołek końcowy krawędzi
  // cp - przepustowość krawędzi

  for(i = 0; i < m; i++)
  {
    // Najpierw odczytujemy te trzy liczby

    cin >> u >> v >> cp;

    // Tworzymy nowy element listy

    x = new slistEl;

    // Wypełniamy jego pola danych

    x->v = v;
    x->c = cp;
    x->f = 0;                     // Zerujemy przepływ

    // Element dołączamy do listy sąsiadów wierzchołka u

    x->next = L[u];
    L[u] = x;
  }

  // Na koniec odczytujemy numery wierzchołków źródła i ujścia

  cin >> s >> t;

  //**************************************************
  //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
  //**************************************************

  // Zerujemy wartość maksymalnego przepływu sieciowego

  fmax = 0;

  // Tworzymy w grafie strukturę sieci rezydualnej

  for(u = 0; u < n; u++)
  {
    for(x = L[u]; x; x = x->next)
    {
      // Sprawdzamy, czy na liście sąsiadów x jest wierzchołek u.
      // Jeśli tak, to krawędź zwrotna istnieje i nie ma potrzeby
      // jej tworzenia.

      test = false;               // Zakładamy brak krawędzi zwrotnej
      for(z = L[x->v]; z; z = z->next)
        if(z->v == u)
        {
          test = true; break;
        }
      if(test) continue;          // Jeśli jest krawędź, sprawdzamy kolejnego sąsiada

      // Tworzymy krawędź zwrotną

      z = new slistEl;
      z->v = u;
      z->c = z->f = 0;
      z->next = L[x->v];
      L[x->v] = z;
    }
  }

  // Sieć rezydualna została utworzona. Teraz zajmiemy się wyznaczeniem
  // maksymalnych przepływów w sieci.

  while(1)
  {
    for(i = 0; i < n; i++)
      P[i] = -1;                  // Zerujemy tablicę poprzedników

    CFP[s] = MAXINT;              // Przepustowość źródła jest nieskończona

    while(!Q.empty()) Q.pop();    // Zerujemy kolejkę

    Q.push(s);                    // W kolejce umieszczamy źródło s

    // Szukamy ścieżki w sieci rezudualnej od źródła s do ujścia t

    while(!Q.empty())
    {
      test = false;             // Zakładamy brak takiej ścieżki
      u = Q.front(); Q.pop();   // Pobieramy wierzchołek z kolejki

      // Przeglądamy listę sąsiadów wierzchołka u

      for(x = L[u]; x; x = x->next)
      {
        // Wyznaczamy przepustowość rezydualną kanału

        cp = x->c - x->f;

        // Przetwarzamy tylko istniejące i nieodwiedzone jeszcze krawędzie

        if(cp && (P[x->v] == -1))
        {
          // Zapamiętujemy poprzednik na ścieżce

          P[x->v] = u;

          // Obliczamy przepustowość rezydualną do węzła x->v

          CFP[x->v] = cp < CFP[u] ? cp : CFP[u];

          // Sprawdzamy, czy ścieżka sięga do ujścia

          if(x->v == t)
          {
             test = true;         // Sygnalizujemy znalezioną ścieżkę
             break;               // Wychodzimy z pętli for
          }
          else Q.push(x->v);      // Inaczej umieszczamy w kolejce wierzchołek x->v
        }
      }

      if(test) break;             // Jeśli jest ścieżka, wychodzimy z pętli while
    }

    if (!test) break;             // Jeśli brak ścieżki, kończymy algorytm

    // Zwiększamy przepływ sieciowy

    fmax += CFP[t];

    // Cofamy się po ścieżce od ujścia t do źródła s

    for(v = t; v != s; v = u)
    {
      u = P[v];                   // u jest poprzednikiem v na ścieżce

      // Szukamy na liście sąsiadów u krawędzi prowadzącej do v.

      for(z = L[u]; z; z = z->next)
        if(z->v == v)
        {
          z->f += CFP[t];         // W kierunku zgodnym ze ścieżką zwiększamy przepływ
          break;
        }

      // Szukamy na liście sąsiadów v krawędzi prowadzącej do u.

      for(z = L[v]; z; z = z->next)
        if(z->v == u)
        {
          z->f -= CFP[t];         // W kierunku przeciwnym do ścieżki zmnejszamy przepływ
          break;
        }
    }
  }

  // Prezentujemy wyniki obliczeń. Najpierw wypisujemy
  // wartość maksymalnego przepływu

  cout << "\nfmax = " << fmax << endl << endl;

  // Następnie wypisujemy znalezione przez algorytm przepływy w
  // kanałach pierwotnej sieci przepływowej. Kanały rozpoznajemy
  // po niezerowej wartości ich przepustowości.

  for(i = 0; i < n; i++)
    for(z = L[i]; z; z = z->next)
      if(z->c)
        cout << i << " -> " << z->v << " " << z->f << ":" << z->c << endl;

  cout << endl;

  // Koniec, usuwamy struktury dynamiczne

  for(i = 0; i < n; i++)
  {
    x = L[i];
    while(x)
    {
      z = x;
      x = x->next;
      delete z;
    }
  }

  delete [] L;
  delete [] P;
  delete [] CFP;

  return 0;
}
Free Basic
' Maksymalny przepływ - algorytm Edmondsa-Karpa
' Data: 24.08.2014
' (C)2014 mgr Jerzy Wałaszek
'----------------------------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type slistEl
  next As slistEl Ptr
  v As Integer
  c As Integer
  f As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal x As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

Dim As Integer m,n                ' Liczba krawędzi i wierzchołków w grafie
Dim As slistEl Ptr Ptr L          ' Tablica list sąsiedztwa
Dim As Integer s,t                ' Numer wierzchołka źródła s i ujscia t
Dim As Integer fmax               ' Maksymalny przepływ sieciowy
Dim As queue Q                    ' Kolejka
Dim As Integer Ptr P              ' Tablica poprzedników
Dim As Integer Ptr CFP            ' Tablica przepustowości rezydualnych dla ścieżek
Dim As Integer i,cp,u,v           ' Zmienne pomocnicze
Dim As slistEl Ptr x,z            ' Wskaźniki elementów listy sąsiedztwa
Dim As Integer test

' Najpierw odczytujemy liczbę wierzchołków i krawędzi grafu

Open Cons For Input As #1

Input #1,n,m

' Tworzymy i inicjujemy struktury dynamiczne

L = New slistEl Ptr [n]           ' Tablica wskaźników list
For i = 0 To n - 1
  L[i] = 0                        ' Tablicę wypełniamy pustymi listami
Next

P = New Integer [n]
CFP = New Integer [n]

' Teraz wczytujemy definicje poszczególnych krawędzi grafu.
' Każda krawędź jest zdefiniowana przez trzy liczby u, v i cp:
' u  - wierzchołek początkowy krawędzi
' v  - wierzchołek końcowy krawędzi
' cp - przepustowość krawędzi

For i = 1 To m
  ' Najpierw odczytujemy te trzy liczby

  Input #1,u,v,cp

  ' Tworzymy nowy element listy

  x = New slistEl

  ' Wypełniamy jego pola danych

  x->v = v
  x->c = cp
  x->f = 0                        ' Zerujemy przepływ

  ' Element dołączamy do listy sąsiadów wierzchołka u

  x->next = L[u]
  L[u] = x
Next

' Na koniec odczytujemy numery wierzchołków źródła i ujścia

Input #1,s,t

'**************************************************
'** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
'**************************************************

' Zerujemy wartość maksymalnego przepływu sieciowego

fmax = 0

' Tworzymy w grafie strukturę sieci rezydualnej

For u = 0 To n - 1
  x = L[u]
  While x
    ' Sprawdzamy, czy na liście sąsiadów x jest wierzchołek u.
    ' Jeśli tak, to krawędź zwrotna istnieje i nie ma potrzeby
    ' jej tworzenia.

    test = 0                      ' Zakładamy brak krawędzi zwrotnej
    z = L[x->v]
    While z
      If z->v = u Then
        test = 1
        Exit While
      End If
      z = z->Next
    Wend

    If test = 0 Then              ' Jeśli brak krawędzi, tworzymy ją
      z = New slistEl
      z->v = u
      z->c = z->f = 0
      z->next = L[x->v]
      L[x->v] = z
    End If
    
    x = x->Next
  Wend
Next

' Sieć rezydualna została utworzona. Teraz zajmiemy się wyznaczeniem
' maksymalnych przepływów w sieci.

While 1
  For i = 0 To n - 1
    P[i] = -1                     ' Zerujemy tablicę poprzedników
  Next

  CFP[s] = MAXINT                 ' Przepustowość źródła jest nieskończona

  While Not Q.empty()
  	 Q.pop()                       ' Zerujemy kolejkę
  Wend

  Q.push(s)                       ' W kolejce umieszczamy źródło s

  ' Szukamy ścieżki w sieci rezudualnej od źródła s do ujścia t

  While Not Q.empty()
    test = 0                      ' Zakładamy brak takiej ścieżki
    u = Q.front(): Q.pop()        ' Pobieramy wierzchołek z kolejki

    ' Przeglądamy listę sąsiadów wierzchołka u

    x = L[u]
    While x

      ' Wyznaczamy przepustowość rezydualną kanału

      cp = x->c - x->f

      ' Przetwarzamy tylko istniejące i nieodwiedzone jeszcze krawędzie

      If (cp <> 0) AndAlso (P[x->v] = -1) Then

        ' Zapamiętujemy poprzednik na ścieżce

        P[x->v] = u

        ' Obliczamy przepustowość rezydualną do węzła x->v

        If cp < CFP[u] Then
        	 CFP[x->v] = cp
        Else
        	 CFP[x->v] = CFP[u]
        EndIf

        ' Sprawdzamy, czy ścieżka sięga do ujścia

        If x->v = t Then
          test = 1                ' Sygnalizujemy znalezioną ścieżkę
          Exit While              ' Wychodzimy z pętli
        Else
          Q.push(x->v)            ' Inaczej umieszczamy w kolejce wierzchołek x->v
        End If
        
      End If
        
      x = x->Next
        
    Wend

    If test Then Exit While       ' Jeśli jest ścieżka, wychodzimy z pętli while
  Wend

  if Not test Then Exit While     ' Jeśli brak ścieżki, kończymy algorytm

  ' Zwiększamy przepływ sieciowy

  fmax += CFP[t]

  ' Cofamy się po ścieżce od ujścia t do źródła s

  v = t
  While v <> s
    u = P[v]                    ' u jest poprzednikiem v na ścieżce

    ' Szukamy na liście sąsiadów u krawędzi prowadzącej do v.

    z = L[u]
    While z
      If z->v = v Then
        z->f += CFP[t]          ' W kierunku zgodnym ze ścieżką zwiększamy przepływ
        Exit While
      End If
      z = z->Next
    Wend

    ' Szukamy na liście sąsiadów v krawędzi prowadzącej do u.

    z = L[v]
    While z
      If z->v = u Then
        z->f -= CFP[t]         ' W kierunku przeciwnym do ścieżki zmnejszamy przepływ
        Exit While
      End If
      z = z->Next
    Wend
      
    v = u
  Wend
    
Wend

' Prezentujemy wyniki obliczeń. Najpierw wypisujemy
' wartość maksymalnego przepływu

Print
Print "fmax =";fmax
Print

' Następnie wypisujemy znalezione przez algorytm przepływy w
' kanałach pierwotnej sieci przepływowej. Kanały rozpoznajemy
' po niezerowej wartości ich przepustowości.

For i = 0 To n - 1
  z = L[i]
  While z
    If z->c Then Print Using "& -> & &:&";i;z->v;z->f;z->c
    z = z->Next
  Wend
Next
Print

' Koniec, usuwamy struktury dynamiczne

For i = 0 To n - 1
  x = L[i]
  While x
    z = x
    x = x->Next
    Delete z
  Wend
Next

Delete [] L
Delete [] P
Delete [] CFP

End
Wynik
7 11
0 1 7 0 3 3
1 3 4 1 4 6
2 0 9 2 5 9
3 4 9 3 6 2
5 3 3 5 6 6
6 4 8
2 4

fmax = 18

0 -> 3 3:3
0 -> 1 6:7
1 -> 4 6:6
1 -> 3 0:4
2 -> 5 9:9
2 -> 0 9:9
3 -> 6 0:2
3 -> 4 6:9
5 -> 6 6:6
5 -> 3 3:3
6 -> 4 6:8

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.