L'algoritmo Ford-Fulkerson è un algoritmo ampiamente utilizzato per risolvere il problema del flusso massimo in una rete di flusso. Il problema del flusso massimo implica determinare la quantità massima di flusso che può essere inviata da un vertice sorgente a un vertice pozzo in un grafo ponderato diretto, soggetto a vincoli di capacità sugli archi.
L'algoritmo funziona trovando iterativamente un percorso aumentante, che è un percorso dalla sorgente al pozzo nel grafo residuo, ovvero il grafico ottenuto sottraendo il flusso di corrente dalla capacità di ciascun bordo. L'algoritmo quindi aumenta il flusso lungo questo percorso della massima quantità possibile, ovvero la capacità minima dei bordi lungo il percorso.
Problema:
Dato un grafico che rappresenta una rete di flusso in cui ogni arco ha una capacità. Inoltre, dati due vertici fonte 'sabbia lavello ‘t’ nel grafico, trovare il massimo flusso possibile da s a t con i seguenti vincoli:
- Il flusso su un bordo non supera la capacità data del bordo.
- Il flusso in entrata è uguale al flusso in uscita per ogni vertice tranne s e t.
Ad esempio, considera il seguente grafico tratto dal libro CLRS.
La portata massima possibile nel grafico sopra è 23.
Pratica consigliata Trova il flusso massimo Provalo!
Prerequisito: Introduzione al problema del flusso massimo
Algoritmo di Ford-Fulkerson
Quella che segue è una semplice idea dell'algoritmo Ford-Fulkerson:
- Inizia con il flusso iniziale pari a 0.
- Sebbene esista un percorso aumentante dalla sorgente al pozzo:
- Trova un percorso aumentante utilizzando qualsiasi algoritmo di ricerca del percorso, come la ricerca in ampiezza o la ricerca in profondità.
- Determinare la quantità di flusso che può essere inviata lungo il percorso aumentante, ovvero la capacità residua minima lungo i bordi del percorso.
- Aumentare il flusso lungo il percorso aumentante della quantità determinata.
- Restituisce il flusso massimo.
Complessità temporale: La complessità temporale dell'algoritmo di cui sopra è O(max_flow * E). Eseguiamo un ciclo mentre è presente un percorso aumentante. Nel peggiore dei casi, potremmo aggiungere 1 unità di flusso in ogni iterazione. Pertanto la complessità temporale diventa O(max_flow * E).
Come implementare il semplice algoritmo di cui sopra?
Definiamo innanzitutto il concetto di grafico residuo necessario per comprendere l'implementazione.
Grafico residuo di una rete di flusso è un grafico che indica ulteriori possibili flussi. Se nel grafo residuo è presente un percorso dalla sorgente al pozzo, è possibile aggiungere il flusso. Ogni bordo di un grafico residuo ha un valore chiamato capacità residua che è uguale alla capacità originale del bordo meno il flusso di corrente. La capacità residua è fondamentalmente la capacità attuale del bordo.
Parliamo ora dei dettagli di implementazione. La capacità residua è 0 se non c'è alcun bordo tra due vertici del grafico residuo. Possiamo inizializzare il grafico residuo come grafico originale poiché non vi è alcun flusso iniziale e la capacità residua inizialmente è uguale alla capacità originale. Per trovare un percorso aumentante, possiamo eseguire un BFS o un DFS del grafo residuo. Abbiamo utilizzato BFS nell'implementazione seguente. Utilizzando BFS, possiamo scoprire se esiste un percorso dalla sorgente al sink. BFS crea anche l'array parent[] . Utilizzando l'array parent[], attraversiamo il percorso trovato e troviamo il possibile flusso attraverso questo percorso trovando la capacità residua minima lungo il percorso. Successivamente aggiungiamo il flusso del percorso trovato al flusso complessivo.
La cosa importante è che dobbiamo aggiornare le capacità residue nel grafico residuo. Sottraiamo il flusso del percorso da tutti i bordi lungo il percorso e aggiungiamo il flusso del percorso lungo i bordi inversi. Dobbiamo aggiungere il flusso del percorso lungo i bordi inversi perché in seguito potrebbe essere necessario inviare il flusso nella direzione opposta (vedere l'esempio del collegamento seguente).
Di seguito è riportata l'implementazione dell'algoritmo Ford-Fulkerson. Per semplificare le cose, il grafico è rappresentato come una matrice 2D.
C++
// C++ program for implementation of Ford Fulkerson> // algorithm> #include> #include> #include> #include> using> namespace> std;> // Number of vertices in given graph> #define 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 */> bool> bfs(>int> rGraph[V][V],>int> s,>int> t,>int> parent[])> {> >// Create a visited array and mark all vertices as not> >// visited> >bool> visited[V];> >memset>(visited, 0,>sizeof>(visited));> >// Create a queue, enqueue source vertex and mark source> >// vertex as visited> >queue<>int>>q;> >q.push(s);> >visited[s] =>true>;> >parent[s] = -1;> >// Standard BFS Loop> >while> (!q.empty()) {> >int> u = q.front();> >q.pop();> >for> (>int> v = 0; v if (visited[v] == false && rGraph[u][v]>0) { // Se troviamo una connessione al nodo sink, // allora non ha più senso in BFS. Dobbiamo // solo impostare il suo genitore e possiamo restituire // true if (v == t) { parent[ v] = u; restituisce vero; } q.push(v); genitore[v] = u; visitato[v] = vero; } } } // Non abbiamo raggiunto il sink in BFS partendo dal sorgente, quindi // return false return false; } // Restituisce il flusso massimo da s a t nel grafico dato int fordFulkerson(int graph[V][V], int s, int t) { int u, v; // Crea un grafico residuo e riempie il grafico residuo // con le capacità date nel grafico originale come // capacità residue nel grafico residuo int rGraph[V] [V]; // Grafico residuo dove rGraph[i][j] // indica la capacità residua del bordo // da i a j (se c'è un bordo. Se // rGraph[i][j] è 0, allora non c'è) for (u = 0; u for (v = 0; v rGraph[u][v] = graph[u][v]; int parent[V]; // Questo array è riempito da BFS e // memorizza il percorso int max_flow = 0; // Inizialmente non c'è flusso // Aumenta il flusso mentre c'è il percorso dalla sorgente al // sink while (bfs(rGraph, s, t, parent)) { // Trova la capacità residua minima dei bordi lungo // il percorso riempito da BFS Oppure possiamo dire trovare il // flusso massimo attraverso il percorso trovato. int path_flow = INT_MAX; v != s; v = parent[v]) { u = parent[v]; path_flow = min(path_flow, rGraph[u][v]); // aggiorna le capacità residue degli spigoli e // inverte gli spigoli lungo il percorso per (v = t; v != s; v = genitore[v]) { u = genitore[v]; rGraph[u][v] -= percorso_flusso; rGraph[v][u] += percorso_flusso } // Aggiungi il flusso del percorso al flusso complessivo max_flow += percorso_flusso } // Restituisce il flusso complessivo return max_flow; } // Programma driver per testare le funzioni di cui sopra int main() { // Creiamo un grafico mostrato nell'esempio sopra 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<< 'The maximum possible flow is ' << fordFulkerson(graph, 0, 5); return 0; }> |
>
>
Giava
// Java program for implementation of Ford Fulkerson> // algorithm> import> java.io.*;> import> java.lang.*;> import> java.util.*;> import> java.util.LinkedList;> class> MaxFlow {> >static> final> 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 */> >boolean> bfs(>int> rGraph[][],>int> s,>int> t,>int> parent[])> >{> >// Create a visited array and mark all vertices as> >// not visited> >boolean> visited[] =>new> boolean>[V];> >for> (>int> i =>0>; i visited[i] = false; // Create a queue, enqueue source vertex and mark // source vertex as visited LinkedList queue = new LinkedList(); queue.add(s); visited[s] = true; parent[s] = -1; // Standard BFS Loop while (queue.size() != 0) { int u = queue.poll(); for (int v = 0; v if (visited[v] == false && rGraph[u][v]>0) { // Se troviamo una connessione al nodo sink //, allora non ha più senso in BFS // Dobbiamo solo impostare il suo genitore // e possiamo restituire true if (v == t) { parent[ v] = u; restituisce vero; } coda.add(v); genitore[v] = u; visitato[v] = vero; } } } // Non abbiamo raggiunto il sink in BFS partendo dal sorgente, // quindi return false return false; } // Restituisce il flusso massimo da s a t nel // dato graph int fordFulkerson(int graph[][], int s, int t) { int u, v; // Crea un grafico residuo e riempie il // grafico residuo con le capacità date nel grafico originale // come capacità residue nel grafico residuo // Grafico residuo dove rGraph[i][j] indica // la capacità residua del bordo da i a j (se // c'è un bordo. Se rGraph[i][j] è 0, allora // non c'è) int rGraph[][] = new int[V][V]; for (u = 0; u for (v = 0; v rGraph[u][v] = graph[u][v]; // Questo array è riempito da BFS e per memorizzare il percorso int parent[] = new int[ V]; int max_flow = 0; // Inizialmente non c'è flusso // Aumenta il flusso mentre c'è il percorso dalla sorgente // al sink while (bfs(rGraph, s, t, parent)) { // Trova la capacità residua minima degli archi // lungo il percorso riempito da BFS Oppure possiamo dire // trovare il flusso massimo attraverso il percorso trovato ]) { u = parent[v]; path_flow = Math.min(path_flow, rGraph[u][v]); } // aggiorna le capacità residue degli spigoli e // inverte gli spigoli lungo il percorso per (v = t; v != s; v = genitore[v]) { u = genitore[v]; rGraph[u][v] -= rGraph[v][u] += path_flow } // Aggiungi il flusso del percorso al totale flow max_flow += path_flow; } // Restituisce il flusso complessivo return max_flow; } // Programma driver per testare le funzioni sopra public static void main(String[] args) raises java.lang.Exception { // Creiamo un grafico mostrato nell'esempio sopra 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 } }; FlussoMax m = nuovo FlussoMax(); System.out.println('Il flusso massimo possibile è ' + m.fordFulkerson(graph, 0, 5)); } }> |
>
>
Pitone
raggruppamento
# 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> |
>
>
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 |
>
>
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) { // Se troviamo una connessione al nodo sink //, allora non ha più senso in BFS // Dobbiamo solo impostare il suo genitore // e possiamo restituire true if (v == t) { parent[ v] = u; restituisce vero; } coda.push(v); genitore[v] = u; visitato[v] = vero; } } } // Non abbiamo raggiunto il sink in BFS partendo // dall'origine, quindi return false return false; } // Restituisce il flusso massimo da s a t nella // data funzione grafica fordFulkerson(graph, s, t) { let u, v; // Crea un grafico residuo e riempie il // grafico residuo con le capacità date // nel grafico originale come residuo // capacità nel grafico residuo // Grafico residuo dove rGraph[i][j] // indica la capacità residua del bordo / / da i a j (se c'è un bordo. // Se rGraph[i][j] è 0, allora // non c'è) let rGraph = new Array(V); for(u = 0; u { rGraph[u] = new Array(V); for(v = 0; v rGraph[u][v] = graph[u][v]; } // Questo array è riempito da BFS e per memorizzare il percorso let parent = new Array(V); // Inizialmente non c'è flusso let max_flow = 0; // Aumenta il flusso mentre // c'è il percorso dall'origine al sink while (bfs(rGraph, s, t , parent)) { // Trova la capacità residua minima dei bordi // lungo il percorso riempito da BFS Oppure possiamo dire // trova il flusso massimo attraverso il percorso trovato let path_flow = Number.MAX_VALUE; ; v != s; v = parent[v]) { u = path_flow = Math.min(path_flow, rGraph[u][v]); invertire i bordi lungo il percorso for(v = t; v != s; v = genitore[v]) { u = genitore[v]; rGraph[u][v] -= rGraph[v][u] + = path_flow; } // Aggiungi il flusso del percorso al flusso complessivo max_flow += path_flow; } // Restituisce il flusso complessivo return max_flow; , 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('Il flusso massimo possibile è ' + fordFulkerson(graph, 0, 5)); // Questo codice è stato fornito da avanitrachhadiya2155> |
>
>Produzione
The maximum possible flow is 23>
Complessità temporale: O(|V| * E^2) ,dove E è il numero di spigoli e V è il numero di vertici.
Complessità spaziale:O(V), mentre creavamo la coda.
L'implementazione di cui sopra dell'algoritmo Ford Fulkerson è chiamata Algoritmo di Edmonds-Karp . L'idea di Edmonds-Karp è quella di utilizzare BFS nell'implementazione Ford Fulkerson poiché BFS sceglie sempre un percorso con un numero minimo di spigoli. Quando si utilizza BFS, la complessità temporale del caso peggiore può essere ridotta a O(VE2). L'implementazione di cui sopra utilizza la rappresentazione della matrice di adiacenza anche se dove BFS prende O(V2) tempo, la complessità temporale dell'implementazione di cui sopra è O(EV3) (Fare riferimento Libro CLRS per la prova della complessità temporale)
Questo è un problema importante poiché si presenta in molte situazioni pratiche. Gli esempi includono la massimizzazione del trasporto con determinati limiti di traffico, la massimizzazione del flusso di pacchetti nelle reti di computer.
Algoritmo di Dinc per il flusso massimo.
Esercizio:
Modificare l'implementazione precedente in modo che venga eseguita in O(VE2) tempo.