L'algorisme de Ford-Fulkerson és un algorisme molt utilitzat per resoldre el problema de flux màxim en una xarxa de flux. El problema de flux màxim consisteix a determinar la quantitat màxima de flux que es pot enviar des d'un vèrtex font a un vèrtex d'aigua en un gràfic ponderat dirigit, subjecte a les restriccions de capacitat a les vores.

L'algorisme funciona trobant iterativament un camí augmentant, que és un camí des de la font fins a l'embornal en el gràfic residual, és a dir, el gràfic obtingut restant el flux de corrent de la capacitat de cada aresta. Aleshores, l'algorisme augmenta el flux al llarg d'aquest camí en la màxima quantitat possible, que és la capacitat mínima de les vores al llarg del camí.

propietats àcides

Problema:

Donat un gràfic que representa una xarxa de flux on cada aresta té una capacitat. A més, donats dos vèrtexs font ‘s’ i pica 't' al gràfic, trobeu el flux màxim possible de s a t amb les restriccions següents:

• El flux en una vora no supera la capacitat donada de la vora.
• El flux entrant és igual al flux sortint per a cada vèrtex excepte s i t.

Per exemple, considereu el gràfic següent del llibre CLRS.

El cabal màxim possible al gràfic anterior és 23.

Requisit previ: Introducció al problema de flux màxim

Algoritme Ford-Fulkerson

La següent és una idea senzilla de l'algorisme de Ford-Fulkerson:

1. Comenceu amb el flux inicial com a 0.
2. Tot i que existeix un camí augmentant des de la font fins a la pica:
   • Trobeu un camí d'augment mitjançant qualsevol algorisme de cerca de camins, com ara la cerca de l'amplada primer o la cerca de la profunditat.
   • Determineu la quantitat de flux que es pot enviar al llarg del camí d'augment, que és la capacitat residual mínima al llarg de les vores del camí.
   • Augmenteu el cabal al llarg del camí d'augment en la quantitat determinada.
3. Retorna el cabal màxim.

Complexitat temporal: La complexitat temporal de l'algorisme anterior és O(max_flow * E). Fem un bucle mentre hi ha un camí que augmenta. En el pitjor dels casos, podem afegir 1 unitat de flux en cada iteració. Per tant, la complexitat temporal esdevé O(max_flow * E).

Com implementar l'algoritme senzill anterior?
Primer definim el concepte de gràfic residual que és necessari per entendre la implementació.

Gràfic Residual d'una xarxa de flux és un gràfic que indica un possible flux addicional. Si hi ha un camí des de la font fins a l'embornal al gràfic residual, és possible afegir flux. Cada aresta d'un gràfic residual té un valor anomenat capacitat residual que és igual a la capacitat original de la vora menys el flux de corrent. La capacitat residual és bàsicament la capacitat actual de la vora.

Parlem ara dels detalls de la implementació. La capacitat residual és 0 si no hi ha cap aresta entre dos vèrtexs del gràfic residual. Podem inicialitzar el gràfic residual com a gràfic original ja que no hi ha flux inicial i la capacitat residual inicialment és igual a la capacitat original. Per trobar un camí augmentant, podem fer un BFS o DFS del gràfic residual. Hem utilitzat BFS a la implementació següent. Utilitzant BFS, podem esbrinar si hi ha un camí des de la font fins a l'enfonsament. BFS també crea matriu pare[]. Utilitzant la matriu pare[], travessem el camí trobat i trobem el possible flux per aquest camí trobant la capacitat residual mínima al llarg del camí. Més tard afegim el flux del camí trobat al flux global.

L'important és que hem d'actualitzar les capacitats residuals al gràfic residual. Restem el flux del camí de totes les vores al llarg del camí i afegim el flux del camí al llarg de les vores inverses Hem d'afegir el flux del camí al llarg de les vores inverses perquè més tard pot ser necessari enviar el flux en direcció inversa (vegeu l'enllaç següent per exemple).

A continuació es mostra la implementació de l'algorisme Ford-Fulkerson. Per simplificar les coses, el gràfic es representa com una matriu 2D.

C++

>

>

Java

Rajinikanth

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Python program for implementation> # of Ford Fulkerson algorithm> from> collections>import> defaultdict> # This class represents a directed graph> # using adjacency matrix representation> class> Graph:> >def> __init__(>self>, graph):> >self>.graph>=> graph># residual graph> >self>. ROW>=> len>(graph)> ># self.COL = len(gr[0])> >'''Returns true if there is a path from source 's' to sink 't' in> >residual graph. Also fills parent[] to store the path '''> >def> BFS(>self>, s, t, parent):> ># Mark all the vertices as not visited> >visited>=> [>False>]>*>(>self>.ROW)> ># Create a queue for BFS> >queue>=> []> ># Mark the source node as visited and enqueue it> >queue.append(s)> >visited[s]>=> True> ># Standard BFS Loop> >while> queue:> ># Dequeue a vertex from queue and print it> >u>=> queue.pop(>0>)> ># Get all adjacent vertices of the dequeued vertex u> ># If a adjacent has not been visited, then mark it> ># visited and enqueue it> >for> ind, val>in> enumerate>(>self>.graph[u]):> >if> visited[ind]>=>=> False> and> val>>0>:> ># If we find a connection to the sink node,> ># then there is no point in BFS anymore> ># We just have to set its parent and can return true> >queue.append(ind)> >visited[ind]>=> True> >parent[ind]>=> u> >if> ind>=>=> t:> >return> True> ># We didn't reach sink in BFS starting> ># from source, so return false> >return> False> > > ># Returns the maximum flow from s to t in the given graph> >def> FordFulkerson(>self>, source, sink):> ># This array is filled by BFS and to store path> >parent>=> [>->1>]>*>(>self>.ROW)> >max_flow>=> 0> # There is no flow initially> ># Augment the flow while there is path from source to sink> >while> self>.BFS(source, sink, parent) :> ># Find minimum residual capacity of the edges along the> ># path filled by BFS. Or we can say find the maximum flow> ># through the path found.> >path_flow>=> float>(>'Inf'>)> >s>=> sink> >while>(s !>=> source):> >path_flow>=> min> (path_flow,>self>.graph[parent[s]][s])> >s>=> parent[s]> ># Add path flow to overall flow> >max_flow>+>=> path_flow> ># update residual capacities of the edges and reverse edges> ># along the path> >v>=> sink> >while>(v !>=> source):> >u>=> parent[v]> >self>.graph[u][v]>->=> path_flow> >self>.graph[v][u]>+>=> path_flow> >v>=> parent[v]> >return> max_flow> > # Create a graph given in the above diagram> graph>=> [[>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>]]> g>=> Graph(graph)> source>=> 0>; sink>=> 5> > print> (>'The maximum possible flow is %d '> %> g.FordFulkerson(source, sink))> # This code is contributed by Neelam Yadav> 
 
 
 
 
    
apilar en java
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C# program for implementation> // of Ford Fulkerson algorithm> using> System;> using> System.Collections.Generic;> public> class> MaxFlow {> >static> readonly> int> V = 6;>// Number of vertices in> >// graph> >/* Returns true if there is a path> >from source 's' to sink 't' in residual> >graph. Also fills parent[] to store the> >path */> >bool> bfs(>int>[, ] rGraph,>int> s,>int> t,>int>[] parent)> >{> >// Create a visited array and mark> >// all vertices as not visited> >bool>[] visited =>new> bool>[V];> >for> (>int> i = 0; i   visited[i] = false;  // Create a queue, enqueue source vertex and mark  // source vertex as visited  List cua = llista nova ();  cua.Afegir(s);  visitat[s] = cert;  pare[s] = -1;  // Bucle BFS estàndard while (queue.Count != 0) { int u = queue[0];  queue.RemoveAt(0);  for (int v = 0; v if (visited[v] == false && rGraph[u, v]> 0) { // Si trobem una connexió amb el node sink //, aleshores no hi ha cap punt a BFS / / ja només hem de configurar el seu pare // i podem retornar true if (v == t) { parent[v] = u } queue.Add(v] = u; v] = true; } } } // No hem arribat al sink a BFS a partir de la font, // retorna false return false } // Retorna el flux màxim // de s a t en el gràfic donat; (int[, ] graph, int s, int t) { int u, v // Crea una gràfica residual i omple // la gràfica residual amb // capacitats donades en la gràfica original com // capacitats residuals en la gràfica /; / Gràfic residual on rGraph[i,j] // indica la capacitat residual de // vora de i a j (si hi ha // vora. Si rGraph[i,j] és 0, aleshores // no n'hi ha) int [, ] rGraph = new int[V, V] for (u = 0; u for (v = 0; v rGraph[u, v] = graph[u, v]; // Aquesta matriu s'omple per BFS i per emmagatzemar el camí int[] pare = nou int[V];  int flux_max = 0; // No hi ha flux inicialment // Augmenta el flux mentre hi ha un camí des de la font // per enfonsar-se mentre (bfs(rGraph, s, t, parent)) { // Troba la capacitat residual mínima de les vores // al llarg del camí omplert per BFS. O podem dir // trobar el cabal màxim pel camí trobat.  int path_flow = int.MaxValue;  per (v = t; v != s; v = pare[v]) { u = pare[v];  flux_camí = Math.Min(flux_camí, rGraph[u, v]);  } // actualitza les capacitats residuals de les vores i // inverteix les vores al llarg del camí per (v = t; v != s; v = pare[v]) { u = pare[v];  rGraph[u, v] -= flux_camí;  rGraph[v, u] += flux_camí;  } // Afegeix el flux del camí al flux global max_flow += path_flow;  } // Retorna el flux global retorn max_flow;  } // Codi del controlador public static void Main() { // Creem un gràfic que es mostra a l'exemple anterior 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 = nou MaxFlow();  Console.WriteLine('El flux màxim possible és ' + m.fordFulkerson(gràfic, 0, 5));  } } /* Aquest codi aportat per PrinciRaj1992 */>
 
 
 
 
    
 
>
 
    
 
>
 
 
Javascript
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // Javascript program for implementation of Ford> // Fulkerson algorithm> // Number of vertices in graph> let V = 6;> // Returns true if there is a path from source> // 's' to sink 't' in residual graph. Also> // fills parent[] to store the path> function> bfs(rGraph, s, t, parent)> {> > >// Create a visited array and mark all> >// vertices as not visited> >let visited =>new> Array(V);> >for>(let i = 0; i   visited[i] = false;  // Create a queue, enqueue source vertex  // and mark source vertex as visited  let queue = [];  queue.push(s);  visited[s] = true;  parent[s] = -1;  // Standard BFS Loop  while (queue.length != 0)  {  let u = queue.shift();  for(let v = 0; v   {  if (visited[v] == false &&   rGraph[u][v]>0) { // Si trobem una connexió amb el // node lavabo, aleshores ja no hi ha cap punt a BFS // Només hem d'establir el seu pare // i podem tornar cert si (v == t) { pare[ v] = u;  retornar veritat;  } queue.push(v);  pare[v] = u;  visitat[v] = cert;  } } } // No hem arribat a l'enfonsament a BFS començant // des de la font, així que retorna false return false; } // Retorna el flux màxim de s a t en // la funció gràfica donada fordFulkerson(graph, s, t) { let u, v;    // Creeu un gràfic residual i ompliu el // gràfic residual amb capacitats donades // a la gràfica original com a residual // capacitats a la gràfica residual // Gràfic residual on rGraph[i][j] // indica la capacitat residual de la vora // / de i a j (si hi ha una vora. // Si rGraph[i][j] és 0, aleshores hi ha // no) deixa rGraph = new Array(V);  for(u = 0; u {rGraph[u] = new Array(V); for(v = 0; v rGraph[u][v] = graph[u][v]; } // Aquesta matriu s'omple per BFS i per emmagatzemar el camí let parent = new Array(V // No hi ha flux inicialment let max_flow = 0 // Augmenta el flux mentre // hi ha un camí de la font a l'enfonsament mentre (bfs(rGraph, s, t); , pare)) { // Trobar la capacitat residual mínima de les vores // al llarg del camí omplert per BFS O podem dir // trobar el flux màxim a través del camí trobat = Number.MAX_VALUE ; v != s; v = parent[v]) { u = parent[v] = Math.min(path_flow, rGraph[u][v] } // Actualitza les capacitats residuals de les vores i // vores inverses al llarg del camí per (v = t; v != s; v = pare[v]) { u = pare[v]; rGraph[u][v] -= path_flow[v][u] + = path_flow } // Afegeix el flux de ruta al flux global max_flow += path_flow } // Retorna el flux global de retorn max_flow } // Codi del controlador // Creem un gràfic que es mostra a l'exemple anterior let graph = [ [ 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 ] ]; document.write('El flux màxim possible és ' + fordFulkerson(graph, 0, 5)); // Aquest codi és aportat per avanitrachhadiya2155>
 
 
 
 
    
 
>
 
    
 
>
 
  Sortida  
 
The maximum possible flow is 23>
 
  Complexitat temporal: O(|V| * E^2) , on E és el nombre d'arestes i V és el nombre de vèrtexs.
 
  Complexitat espacial: O(V), mentre vam crear la cua.
 
La implementació anterior de l'algoritme Ford Fulkerson s'anomena   Algoritme Edmonds-Karp   . La idea d'Edmonds-Karp és utilitzar BFS a la implementació de Ford Fulkerson, ja que BFS sempre tria un camí amb un nombre mínim d'arestes. Quan s'utilitza BFS, la complexitat del temps del pitjor cas es pot reduir a O (VE2). La implementació anterior utilitza la representació matricial d'adjacència, tot i que BFS pren O (V2), la complexitat temporal de la implementació anterior és O(EV3) (Refer Llibre CLRS per provar la complexitat del temps)
 
Aquest és un problema important, ja que sorgeix en moltes situacions pràctiques. Alguns exemples inclouen, maximitzar el transport amb determinats límits de trànsit, maximitzar el flux de paquets a les xarxes d'ordinadors. 
Algoritme de Dinc per a Max-Flow.
una classe pot estendre diverses classes
 
  Exercici:   
Modifiqueu la implementació anterior perquè s'executi en O(VE2) temps.