Ford-Fulkersonov algoritam

Ford-Fulkerson metod (nazvan po L. R. Fordu, ml. i D. R. Fulkersonu je algoritam koji računa maksimalni protok u transportnoj mreži. Objavljen je 1956. Ime "Ford-Fulkerson" se često koristi i za Edmonds-Karp algoritam, koji je specijalizacija Ford-Fulkersona.

Osnovna ideja je jednostavna. Dokle god postoji putanja od izvora (početni čvor) do ponora (krajnji čvor), sa dostupnim kapacitetima na svim granama putanje, slaćemo protok duž jedne od ovih putanja. Tada pronalazimo novu putanju itd. Putanja se dostupnim kapacitetom se naziva pojačavajuća putanja.

Algoritam

Neka je $G(V,E)$ graf i neka za svaku granu od $u$ do $v$ $c(u,v)$ predstavlja kapacitet, a $f(u,v)$ protok duž grane. Mi želimo da pronađemo maksimalan protok od izvora $s$ do ponora $t$ . Nakon svakog koraka u algoritmu, sledeća tvrđenja su tačna:

Ograničenja kapaciteta:	$\forall (u,v)\in E\ f(u,v)\leq c(u,v)$	Protok kroz granu ne može premašiti njen kapacitet.
Kosa simetrija:	$\forall (u,v)\in E\ f(u,v)=-f(v,u)$	Ukupan protok od $u$ do $v$ mora biti suprotan od protoka od $v$ do $u$ (videti primer).
Očuvanje protoka:	$\forall u\in V:u\neq s{\text{ and }}u\neq t\Rightarrow \sum _{w\in V}f(u,w)=0$	Pod uslovom da $u$ nije $s$ ili $t$ . Ukupan protok ka nekom čvoru je nula, osim ako čvor nije izvor, koji "stvara" protok, ili ponor, koji "troši" protok.

Ovo znači da je protok kroz mrežu dozvoljeni protok nakon svakog ponavljanja u algoritmu. Definišemo rezidualnu mrežu $G_{f}(V,E_{f})$ kao mrežu kapaciteta $c_{f}(u,v)=c(u,v)-f(u,v)$ i bez protoka. Obratite pažnju da može da se desi da protok od $v$ do $u$ bude dozvoljen u rezidualnoj mreži, iako nedozvoljen u početnoj mreži: ako $f(u,v)>0$ i $c(v,u)=0$ tada $c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0$ .

Algoritam Ford-Fulkerson

Ulaz Graf

G

sa kapacitetima

c

, izvorom

s

i ponorom

t

Izlaz Protok

f

od

s

do

t

koji je maksimalan

$f(u,v)\leftarrow 0$ za sve grane $(u,v)$
Dok postoji putanja $p$ od $s$ do $t$ u $G_{f}$ , takva da je $c_{f}(u,v)>0$ za sve grane $(u,v)\in p$ :
1. Pronađi $c_{f}(p)=\min\{c_{f}(u,v):(u,v)\in p\}$
2. Za svaku granu $(u,v)\in p$
  1. $f(u,v)\leftarrow f(u,v)+c_{f}(p)$ (Pošalji protok duž putanje)
  2. $f(v,u)\leftarrow f(v,u)-c_{f}(p)$ (Protok se može "vratiti" kasnije)

Putanja iz koraka 2 se može pronaći uz pomoć pretrage u širinu ili pretrage u dubinu u grafu $G_{f}(V,E_{f})$ . Ukoliko koristite pretragu u širinu, onda se zove Edmonds-Karp algoritam.

Kada se više nijedna putanja ne može pronaći, tada se iz $s$ ne može doći do $t$ u rezidualnoj mreži. Ako je $S$ skup čvorova do kojih se može doći u rezidualnoj mreži iz $s$ , onda je ukupan kapacitet početne mreže grana od $S$ do $V$ sa jedne strane jednak ukupnom protoku koji smo pronašli od $s$ do $t$ , a sa druge strane služi kao gornja granica za sve takve protoke. To dokazuje da je protok koji smo pronašli maksimalan.

Glavni primer

Sledeći primer pokazuje prve korake Ford-Fulkersona u protočnoj mreži sa 4 čvora, izvorom $A$ i ponorom $D$ . Ovaj primer pokazuje ponašanje algoritma u najgorem slučaju. U svakom koraku se korz mrežu šalje protok od $1$ . Da smo iskoristili pretragu u širinu, samo dva koraka bi bila potrebna.

Putanja	Kapacitet	Rezultujuća mreža
Početna mreža
$A,B,C,D$	$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D))=$ $\min(c(A,B)-f(A,B),c(B,C)-f(B,C),c(C,D)-f(C,D))=$ $\min(1000-0,1-0,1000-0)=1$
$A,C,B,D$	$\min(c_{f}(A,C),c_{f}(C,B),c_{f}(B,D))=$ $\min(C),c(C,B)-f(C,B),c(B,D)-f(B,D))=$ $\min(1000-0,0-(-1),1000-0)=1$
Nakon još 1998 koraka…
Konačni izgled mreže.

Primetite kako se protok "gura nazad" od $C$ do $B$ kada se traži putanja $A,C,B,D$ .

Nezavršavajući primer

Razmotrite mrežu datu desno, sa izvorom $s$ , ponorom $t$ i kapacitetima grana $e_{1}$ , $e_{2}$ i $e_{3}$ $1$ , $r=({\sqrt {5}}-1)/2$ i $1$ , a kapacitet svih drugih grana je neko $M\geq 2$ . Konstanta $r$ je odabrana, jer $r^{2}=1-r$ . Koristimo pojačavajuće putanje u skladu sa datom tabelom, gde je $p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}$ , $p_{2}=\{s,v_{2},v_{3},v_{4},t\}$ i $p_{3}=\{s,v_{1},v_{2},v_{3},t\}$ .

Korak	Pojačavajuća putanja	Poslat protok	Preostali protok
Korak	Pojačavajuća putanja	Poslat protok	$e_{1}$	$e_{2}$	$e_{3}$
0			$r^{0}=1$	$r$	$1$
1	$\{s,v_{2},v_{3},t\}$	$1$	$r^{0}$	$r^{1}$	$0$
2	$p_{1}$	$r^{1}$	$r^{2}$	$0$	$r^{1}$
3	$p_{2}$	$r^{1}$	$r^{2}$	$r^{1}$	$0$
4	$p_{1}$	$r^{2}$	$0$	$r^{3}$	$r^{2}$
5	$p_{3}$	$r^{2}$	$r^{2}$	$r^{3}$	$0$

Obratite pažnju na to da nakon koraka 1, kao i nakon koraka 5, preostali kapacitet grana $e_{1}$ , $e_{2}$ i $e_{3}$ su u obliku $r^{n}$ , $r^{n+1}$ and $0$ , za neko $n\in \mathbb {N}$ . Ovo znači da možemo koristiti pojačavajuće putanje $p_{1}$ , $p_{2}$ , $p_{1}$ i $p_{3}$ beskonačno mnogo puta i preostali kapacitet ovih grana će uvek imati isti oblik. Ukupan protok u mreži nakon koraka 5 je $1+2(r^{1}+r^{2})$ . Ako nastavimo da koristimo ove pojačavajuće putanje, ukupan protok teži ka $\textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r$ , dok je maksimalan protok $2M+1$ . U ovom slučaju se algoritam nikad ne završava, a protok ni ne teži ka maksimalnom protoku.^[1]

Dodatni primeri

Slika 1.1

Slika 1.2 / Inicijalizacija

Primer 1.

Pronađimo maksimalan protok za mrežu sa Slike 1.1

1. Iteracija :

U koraku 1, postavili smo da za svaki čvor prethodnik i rezerva budu jednaki simbolu -, da rezerva za $a$ bude jednaka " ∞ " i da je S = { $a$ }. Tada imamo mrežu sa Slike 1.2

U koraku 2, proveravamo da skup S nije prazan i biramo $a$ iz S.

U koraku 3, stavljamo da rezerva za $b$ bude jednaka min(7, ∞) = 7 i da prethodnik od $b$ bude čvor $a$ . Smeštamo $b$ u S. Takođe stavljamo da rezerva za $d$ bude jednaka min(6, ∞) = 6, a da prethodnik od $d$ bude jednak $a$ . Smeštamo $d$ u S.

Koraci 4,5 se ne mogu primeniti (4. korak zato što nemamo ni jednu nepravilno orijentisanu granu, a 5. korak jer $z$ nije označen), pa se vraćamo na korak 2.

U koraku 2, proveravamo da skup S nije prazan, a zatim iz S biramo neki čvor, recimo $b$ . Skup S sada sadrži samo $d$

U koraku 3, stavljamo da rezerva za $c$ bude jednaka min(3, 7) = 3 i da prethodnik od $c$ bude čvor $b$ . Smeštamo $c$ u S tako da je S = { $c$ , $d$ }. Ponovo se Koraci 4,5 ne mogu primeniti, tako da se vraćamo na Korak 2.

U koraku 2, proveravamo da skup S nije prazan i biramo neki čvor, recimo $c$ iz S. Skup S ponovo sadrži samo $d$ .

U koraku 3, stavljamo rezervu za $z$ na min(3,5) = 3 i prethodnik od $z$ postaje čvor $c$ . Ne smeštamo $z$ u S.

U koraku 4, označili bismo $d$ ali je već označeno.

U koraku 5, vidimo da je $z$ označeno i koristeći funkciju prethodnika, otkrivamo da imamo lanac $a$ → $b$ → $c$ → $z$ sa težinama grana (7,0) → (3,0) → (5,0) i dodajuci 3, rezervu za $z$ protoku svake grane tj. drugoj kordinati grane, dobijamo lanac $a$ → $b$ → $c$ → $z$ sa tezinama (7,3) → (3,3) → (5,3) što nam daje mrežu sa Slike 1.3.

Slika 1.3

Slika 1.4

2. Iteracija:

Sada se vraćamo na korak 1, gde ponovo podešavamo oznake i prethodnike i neka je S = { $a$ }.

U koraku 2, biramo a iz S.

U koraku 3, podešavamo da rezerva za $b$ bude jednaka min(∞,7-3) = 4 i da prethodnik od $b$ bude čvor $a$ . Smeštamo $b$ u S. Takođe stavljamo da rezerva za $d$ bude jednaka 6 i stavljamo da prethodnik od $d$ bude čvor $a$ . Smeštamo $d$ u S.

Koraci 4,5 se ne mogu primeniti, tako da se vraćamo na korak 2.

U koraku 2, biramo $b$ iz S. Kako protok od $b$ do $c$ jednak kapacitetu grane od $b$ do $c$ , ne možemo da primenimo korak 3 i označimo $c$ .

U koraku 2, biramo $d$ iz S.

U koraku 3, podešavamo da rezerva za $z$ bude jednaka min(6,2) = 2 i da prethodnik od $z$ bude čvor $d$ . Ne smeštamo $z$ u S.

U koraku 5, vidimo da je $z$ označeno i koristeći funkciju prethodnika, otkrivamo da imamo lanac $a$ → $d$ → $z$ sa težinama grana (6,0) → (2,0) i dodajuci 2, rezervu za $z$ protoku svake grane tj. drugoj kordinati grane, dobijamo lanac $a$ → $d$ → $z$ sa težinama grana (6,2) → (2,2) što nam daje mrežu sa Slike 1.4.

Slika 1.5

Slika 1.6

3. Iteracija:

Sada se vraćamo na korak 1 i ponavljamo postupak dok ne dobijemo lanac $a$ → $d$ → $c$ → $z$ sa težinama grana (6,2) → (2,0) → (5,3) i dodajući 2, rezervu od $z$ protoku svake grane, dobijamo lanac $a$ → $d$ → $c$ → $z$ sa težinama grana (6,4) → (2,2) → (5,5) što nam daje Sliku 1.5

4. Iteracija:

Sada se vraćamo na korak 1 gde ponovo poništavamo oznake i prethodnike i postavljamo S = { $a$ }.

U koraku 2, biramo $a$ iz S.

U koraku 3, kao i ranije, stavljamo da rezerva za $b$ bude jednaka 4 i da prethodnik od $d$ bude čvor $a$ . Smeštamo $b$ u S. Takođe stavljamo da rezerva za $d$ bude jednaka 6 - 4 = 2 i smeštamo $d$ u S.

Vraćamo se na korak 2. Biramo $b$ iz S. Kako je protok od $b$ do $c$ jednak kapacitetu grane od $b$ do $c$ , ne možemo da označimo $c$ , tako da treba da se vratimo na korak 2.

Korak 2, biramo $d$ iz S. Kako je protok od $d$ do $c$ jednak njihovom kapacitetu, ne možemo da označimo $c$ i $z$ . Ponovo se vraćamo na korak 2, ali je skup S prazan, tako da smo završili.

Konačan protok prikazan je na Slici 1.6 i on predstavlja zbir protoka u svim iteracijama tj. u ovom slučaju 3 + 2 + 2 = 7.

Slika 2.1

[[Datoteka:Slika 2.2.png|350p|thumbnail|center|Lj

PRIMER 2. (sa nepravilno orijentisanom granom)

Pronađimo maksimalan protok za mrežu sa Slike 2.1

1. Iteracija :

Ovoga puta daćemo manje detalja za nekoliko prvih iteracija.

U prvoj iteraciji označavamo $a$ (-,∞) , $b(a,9)$ , $d(a,8)$ , $c(b,4)$ , $e(b,6)$ , $z(c,4)$ . To nam daje put $a$ - $z$ i dobijamo lanac $a$ → $b$ → $c$ → $z$ sa težinama grana (9,0) → (4,0) → (8,0) i dodajući 4, rezervu od $z$ protoku svake grane, dobijamo lanac $a$ → $b$ → $c$ → $z$ sa težinama grana (9,4) → (4,4) → (8,4) što nam daje Sliku 2.2

Slika 2.3

Slika 2.4

2. Iteracija :

U drugom prolazu označavamo $a$ (-,∞), $b(a,5)$ , $d(a,8)$ , $c(d,4)$ , $e(d,8)$ , $z(e,7)$ . To nam daje put $a$ - $z$ i dobijamo lanac $a$ → $d$ → $e$ → $z$ sa težinama grana (8,0) → (9,0) → (7,0) i dodajući 7, rezervu od $z$ protoku svake grane, dobijamo lanac $a$ → $d$ → $e$ → $z$ sa težinama grana (8,7) → (9,7) → (7,7) što nam daje Sliku 2.3

3. Iteracija :

U trećem prolazu označavamo $a$ (-,∞) , $b(a,5)$ , $d(a,1)$ , $c(d,1)$ , $e(d,1)$ , $z(c,1)$ . To nam daje put $a$ - $z$ i dobijamo lanac $a$ → $d$ → $c$ → $z$ sa težinama grana (8,7) → (4,0) → (8,4) i dodajući 1, rezervu od $z$ protoku svake grane, dobijamo lanac $a$ → $d$ → $c$ → $z$ sa težinama grana (8,8) → (4,1) → (8,5) što nam daje Sliku 2.4.

Slika 2.5

Slika 2.6

4. Iteracija :

Od sada postaje interesantno tako da ćemo obratiti pažnju na detalje. Označavamo $b(a,5)$ ali ne možemo da označimo $d$ i smeštamo samo $b$ u S. Birajući $b$ iz S, ne možemo da označimo $c$ , ali označavamo $e(b,5)$ i smeštamo $e$ u S. Birajući $e$ iz S, ne možemo da označimo $z$ , ali kako $d$ nije označeno, možemo to da učinimo . Kako grana ( $d$ , $e$ ) nije pravilno orijentisana, dopuštamo da rezerva od $d$ bude jednaka min(7,5) = 5. Stavljamo da prethodnik od $d$ bude jednak $e$ i smeštamo $d$ u S (Korak 4. u Postupku). Birajući $d$ iz S, jedini izbor koji imamo je da označimo $c(d,3)$ i smestimo $c$ u S. Biramo $c$ iz S i označavamo $z(c,3)$ .

To nam daje put $a$ - $z$ i dobijamo lanac $a$ → $b$ → $e$ ← $d$ → $c$ → $z$ sa težinama grana (9,4) → (6,0) → (9,7) ← (4,1) → (8,5) i kako je rezerva od $z$ jednaka 3, svakom protoku dodajemo 3, osim onom za granu ( $d$ , $e$ ). Pošto ona nije pravilno orijentisana, oduzimamo 3 od protoka ove grane i dobijamo lanac $a$ → $b$ → $e$ ← $d$ → $c$ → $z$ sa težinama grana (9,7) → (6,3) → (9,4) ← (4,4) → (8,8) što nam daje Sliku 2.5.

5. Iteracija :

Sada možemo da počnemo završni prolaz. Počinjemo sa S = { $a$ }. Uklanjamo $a$ iz S, označavamo $b(a,2)$ i smeštamo $b$ u S. Biramo $b$ iz S, označavamo $e(b,2)$ , $c$ ne možemo da označimo iz $b$ . Smeštamo $e$ u S. Biramo $e$ iz S , označavamo $d(e,2)$ pošto je rezerva od $d$ jednaka minimumu protoka grane ( $d$ , $e$ ) i rezerva od $d$ (Korak 4. u Postupku). Zatim smeštamo $d$ u S. Potom biramo $d$ iz S, ali ne možemo da izvršimo bilo koji od preostalih koraka, pa se vraćamo na korak 2. Ali skup S je prazan, pa završavamo. Sada imamo Sliku 2.6.

Konačan protok prikazan je na Slici 2.6 i on predstavlja zbir protoka u svim iteracijama tj. u ovom slučaju 4 + 7 + 1 + 3 = 15.

Složenost

Dodajući pojačavajuće putanje protoku koji je već utvrđen u grafu doći ćemo do maksimalnog protoka kada više ne budemo mogli da pronađemo nove pojačavajuće putanje. Međutim, ne postoji sigurnost da će se do ove situacije ikad doći, tako da je jedino sigurno da ukoliko se algoritam zaustavi da će odgovor biti tačan. U slučaju da algoritam radi beskonačno, može se desiti da protok uopšte ne konvergira ka maksimalnom protoku. Ali, ova situacija se događa samo sa iracionalnim vrednostima protoka. Kada su kapaciteti celi brojevi, vreme izvršavanja je ograničeno sa $O(Ef)$ (videti veliko O), gde je $E$ broj grana u grafu i $f$ maksimalan protok grafa. Ovo je zato što se pojačavajuća putanja može pronaći u $O(E)$ vremena i povećati protok za celobrojnu vrednost koja je minimum $1$ .

Varijacija Ford-Fulkerson algoritma koji garantuje završetak i vremenski je nezavisna od maksimalnog protoka u grafu je Edmonds-Karp algoritam koji radu vremenu $O(VE^{2})$ .

Pajton implementacija

class Edge(object):
    def __init__(self, u, v, w):
        self.source = u
        self.sink = v  
        self.capacity = w
    def __repr__(self):
        return "%s->%s:%s" % (self.source, self.sink, self.capacity)

class FlowNetwork(object):
    def __init__(self):
        self.adj = {}
        self.flow = {}
 
    def add_vertex(self, vertex):
        self.adj[vertex] = []
 
    def get_edges(self, v):
        return self.adj[v]
 
    def add_edge(self, u, v, w=0):
        if u == v:
            raise ValueError("u == v")
        edge = Edge(u,v,w)
        redge = Edge(v,u,0)
        edge.redge = redge
        redge.redge = edge
        self.adj[u].append(edge)
        self.adj[v].append(redge)
        self.flow[edge] = 0
        self.flow[redge] = 0
 
    def find_path(self, source, sink, path):
        if source == sink:
            return path
        for edge in self.get_edges(source):
            residual = edge.capacity - self.flow[edge]
            if residual > 0 and edge not in path:
                result = self.find_path( edge.sink, sink, path + [edge]) 
                if result != None:
                    return result
 
    def max_flow(self, source, sink):
        path = self.find_path(source, sink, [])
        while path != None:
            residuals = [edge.capacity - self.flow[edge] for edge in path]
            flow = min(residuals)
            for edge in path:
                self.flow[edge] += flow
                self.flow[edge.redge] -= flow
            path = self.find_path(source, sink, [])
        return sum(self.flow[edge] for edge in self.get_edges(source))

Java implementacija

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.LinkedList;
 
class MaxFlow
{
    static final int V = 6; //Broj cvorova grafa
 
    /* Vraca true ako postoji put od pocetnog
        cvora do krajnjeg (cilja) u grafu, 
        takodje popunjava parent[] da zapamti put
       */
    boolean bfs(int rGraph[][], int s, int t, int parent[])
    {
        // Napravi listu posecenih elemenata, na pocetku stavi da su svi
        // neposeceni
        boolean visited[] = new boolean[V];
        for(int i=0; i<V; ++i)
            visited[i]=false;
 
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(s);
        visited[s] = true;
        parent[s]=-1;
 
        // BFS pretraga
        while (queue.size()!=0)
        {
            int u = queue.poll();
 
            for (int v=0; v<V; v++)
            {
                if (visited[v]==false && rGraph[u][v] > 0)
                {
                    queue.add(v);
                    parent[v] = u;
                    visited[v] = true;
                }
            }
        }
 
        // Ako smo dosli do ciljnog cvora u BFS-u onda 
        // vrati true u suprotnom vrati false
        return (visited[t] == true);
    }
 
    // Vraca maksimalni protok od s do t za dati graf
    int fordFulkerson(int graph[][], int s, int t)
    {
        int u, v;
 
        int rGraph[][] = new int[V][V];
 
        for (u = 0; u < V; u++)
            for (v = 0; v < V; v++)
                rGraph[u][v] = graph[u][v];
 
        // Lista je popunjena u BFS- u i pamti puteve
        int parent[] = new int[V];
 
        int max_flow = 0;  // na pocetku je protok 0
 
        // Augmentuj protok dokle god postoji put od izvora do cilja 
        while (bfs(rGraph, s, t, parent))
        {
           
            // Pronadji maksimalan protok za pronadjeni put od s do t
            int path_flow = Integer.MAX_VALUE;
            for (v=t; v!=s; v=parent[v])
            {
                u = parent[v];
                path_flow = Math.min(path_flow, rGraph[u][v]);
            }
 
            // Povecaj kapacitete grana i umanji ako ima onih sa obrnutim smerom, 
            // duz nadjene putanje 
            for (v=t; v != s; v=parent[v])
            {
                u = parent[v];
                rGraph[u][v] -= path_flow;
                rGraph[v][u] += path_flow;
            }
 
            // Dodajemo trenutni protok konacnom maksimalnom protoku kroz mrezu
            max_flow += path_flow;
        }
 
        // Vracamo konacan max protok
        return max_flow;
    }
 
    // Main metod za testiranje algoritma
    public static void main (String[] args) throws java.lang.Exception
    {
        // Kreiramo proizvoljan graf
        int graph[][] =new int[][] { {0, 16, 13, 0, 0, 0},
                                     {0, 0, 10, 12, 0, 0},
                                     {0, 4, 0, 0, 14, 0},
                                     {0, 0, 9, 0, 0, 20},
                                     {0, 0, 0, 7, 0, 4},
                                     {0, 0, 0, 0, 0, 0}
                                   };
        MaxFlow m = new MaxFlow();
 
        System.out.println("Maksimalan protok kroz mrezu je  " +
                           m.fordFulkerson(graph, 0, 5));
 
    }
}

C++ implementacija

#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
 
// Broj cvorova u grafu
#define V 6
 
  /* Vraca true ako postoji put od pocetnog
        cvora do krajnjeg (cilja) u grafu, 
        takodje popunjava parent[] da zapamti put
       */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
    // Napravi listu posecenih elemenata, na pocetku stavi da su svi
    // neposeceni
    bool visited[V];
    memset(visited, 0, sizeof(visited));
 
    queue <int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;
 
    // BFS pretraga
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
 
        for (int v=0; v<V; v++)
        {
            if (visited[v]==false && rGraph[u][v] > 0)
            {
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
 
   // Ako smo dosli do ciljnog cvora u BFS-u onda 
   // vrati true u suprotnom vrati false
    return (visited[t] == true);
}
 
 // Vraca maksimalni protok od s do t za dati graf
int fordFulkerson(int graph[V][V], int s, int t)
{
    int u, v;
 
    int rGraph[V][V]; 
    for (u = 0; u < V; u++)
        for (v = 0; v < V; v++)
             rGraph[u][v] = graph[u][v];
 
    int parent[V]; // Lista je popunjena u BFS- u i pamti puteve

 
    int max_flow = 0;  
 
     // Augmentuj protok dokle god postoji put od izvora do cilja 
    while (bfs(rGraph, s, t, parent))
    {
       // Pronadji maksimalan protok za pronadjeni put od s do t
        int path_flow = INT_MAX;
        for (v=t; v!=s; v=parent[v])
        {
            u = parent[v];
            path_flow = min(path_flow, rGraph[u][v]);
        }
 
        // Povecaj kapacitete grana i umanji ako ima onih sa obrnutim smerom, 
        // duz nadjene putanje 
        for (v=t; v != s; v=parent[v])
        {
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
        }
 
        // Dodaj trenutni protok maksimalnom protoku
        max_flow += path_flow;
    }
 
    // Vrati max protok
    return max_flow;
}
 
// Main funkcija za testiranje algoritma
int main()
{

    int graph[V][V] = { {0, 16, 13, 0, 0, 0},
                        {0, 0, 10, 12, 0, 0},
                        {0, 4, 0, 0, 14, 0},
                        {0, 0, 9, 0, 0, 20},
                        {0, 0, 0, 7, 0, 4},
                        {0, 0, 0, 0, 0, 0}
                      };
 
    cout << "Maksimalan protok kroz mrezu je :  " << fordFulkerson(graph, 0, 5);
 
    return 0;
}

Reference

^ Zwick, Uri (21. 8. 1995). „The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate”. Theoretical Computer Science. 148 (1): 165—170. doi:10.1016/0304-3975(95)00022-O.

Literatura

Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008). „Chapter 8:Network Flow Algorithms”. Algorithms in a Nutshell. Oreilly Media. str. 226—250. ISBN 978-0-596-51624-6.
Anderson, James A. (2004). „Chapter 16:Networks - Ford–Fulkerson algorithm”. Discrete Mathematics with Combinatorics (2nd Edition). Pearson Education. str. 783-789. ISBN 978-0130457912.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „Section 26.2: The Ford-Fulkerson method”. Introduction to Algorithms (Second izd.). MIT Press and McGraw-Hill. str. 651-664. ISBN 978-0-262-03293-3.
Ford, L. R.; Fulkerson, D. R. (1956). „Maximal flow through a network”. Canadian Journal of Mathematics. 8: 399—404.

Spoljašnje veze

[1] Zwick, Uri (21. 8. 1995). „The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate”. Theoretical Computer Science. 148 (1): 165—170. doi:10.1016/0304-3975(95)00022-O.

[1]