Ford-Fulkerson-algoritmen er en mye brukt algoritme for å løse det maksimale strømningsproblemet i et strømningsnettverk. Maksimal strømningsproblemet innebærer å bestemme den maksimale mengden strømning som kan sendes fra et kildetoppunkt til et synkepunkt i en rettet vektet graf, underlagt kapasitetsbegrensninger på kantene.
Algoritmen fungerer ved å iterativt finne en forsterkningsbane, som er en vei fra kilden til synken i restgrafen, dvs. grafen som oppnås ved å trekke strømstrømmen fra kapasiteten til hver kant. Algoritmen øker deretter flyten langs denne banen med størst mulig mengde, som er minimumskapasiteten til kantene langs banen.
Problem:
Gitt en graf som representerer et strømningsnettverk der hver kant har en kapasitet. Også gitt to hjørner kilde 's' og synke 't' i grafen, finn maksimalt mulig flyt fra s til t med følgende begrensninger:
- Strømning på en kant overskrider ikke den gitte kapasiteten til kanten.
- Innkommende strøm er lik utgående strøm for hvert toppunkt bortsett fra s og t.
Tenk for eksempel på følgende graf fra CLRS-boken.
Maksimal mulig flyt i grafen ovenfor er 23.
Anbefalt fremgangsmåte Finn maksimal flyt Prøv det!
Forutsetning: Max Flow Problem Introduksjon
Ford-Fulkerson-algoritmen
Følgende er enkel idé om Ford-Fulkerson-algoritmen:
- Start med innledende flyt som 0.
- Mens det eksisterer en økende vei fra kilden til vasken:
- Finn en utvidelsesbane ved å bruke en hvilken som helst banesøkende algoritme, for eksempel bredde-først-søk eller dybde-først-søk.
- Bestem mengden strømning som kan sendes langs forsterkningsbanen, som er minimum gjenværende kapasitet langs kantene av banen.
- Øk strømmen langs forsterkningsbanen med den bestemte mengden.
- Returner maksimal flyt.
Tidskompleksitet: Tidskompleksiteten til algoritmen ovenfor er O(max_flow * E). Vi kjører en sløyfe mens det er en økende bane. I verste fall kan vi legge til 1 enhetsflyt i hver iterasjon. Derfor blir tidskompleksiteten O(max_flow * E).
Hvordan implementere den ovennevnte enkle algoritmen?
La oss først definere konseptet Residual Graph som er nødvendig for å forstå implementeringen.
Restgraf av et strømningsnettverk er en graf som indikerer ytterligere mulig strømning. Hvis det er en vei fra kilde til synke i gjenværende graf, så er det mulig å legge til flyt. Hver kant av en gjenværende graf har en verdi kalt restkapasitet som er lik originalkapasiteten til kanten minus strømflyt. Restkapasitet er i utgangspunktet den nåværende kapasiteten til kanten.
La oss nå snakke om implementeringsdetaljer. Restkapasiteten er 0 hvis det ikke er noen kant mellom to toppunkter av gjenværende graf. Vi kan initialisere den gjenværende grafen som den opprinnelige grafen siden det ikke er noen innledende flyt og den opprinnelige gjenværende kapasiteten er lik den opprinnelige kapasiteten. For å finne en utvidelsesbane kan vi enten gjøre en BFS eller DFS av gjenværende graf. Vi har brukt BFS i implementeringen nedenfor. Ved hjelp av BFS kan vi finne ut om det er en vei fra kilde til synke. BFS bygger også overordnet [] array. Ved å bruke parent[]-matrisen går vi gjennom den funnet banen og finner mulig flyt gjennom denne banen ved å finne minimum restkapasitet langs banen. Vi legger senere til den funnet baneflyten til den totale flyten.
Det viktige er at vi må oppdatere gjenværende kapasiteter i gjenværende graf. Vi trekker banestrøm fra alle kanter langs banen, og vi legger til banestrøm langs de motsatte kantene. Vi må legge til banestrøm langs motsatte kanter fordi det senere kan være nødvendig å sende strømning i motsatt retning (se følgende lenke for eksempel).
Nedenfor er implementeringen av Ford-Fulkerson-algoritmen. For å gjøre ting enkelt, er grafen representert som en 2D-matrise.
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) { // Hvis vi finner en forbindelse til sink-noden, // så er det ingen vits i BFS lenger. Vi // må bare sette den overordnede og kan returnere // true if (v == t) { parent[ v] = u; return true; } q.push(v); forelder[v] = u; besøkt[v] = sant; } } } // Vi nådde ikke sink i BFS fra kilden, så // returnerer false return false; } // Returnerer maksimal flyt fra s til t i den gitte grafen int fordFulkerson(int graph[V][V], int s, int t) { int u, v; // Lag en restgraf og fyll restgrafen // med gitte kapasiteter i den opprinnelige grafen som // restkapasiteter i gjenværende graf int rGraph[V] [V]; // Restgraf der rGraph[i][j] // indikerer restkapasiteten til kanten // fra i til j (hvis det er en kant. Hvis // rGraph[i][j] er 0, så er det ikke det) for (u = 0; u for (v = 0; v rGraph[u][v] = graf[u][v]; int overordnet[V]; // Denne matrisen fylles av BFS og til // lagre bane int max_flow = 0; // Det er ingen flyt i utgangspunktet // Øk flyten mens det er bane fra kilden til // sink while (bfs(rGraph, s, t, parent)) { // Finn minimum restkapasitet til kantene langs // banen fylt av BFS Eller vi kan si finn // maksimal flyt gjennom banen funnet int path_flow = INT_MAX; v = parent[v] parent[v]; path_flow = min(path_flow, rGraph[u][v] } // oppdater restkapasiteten til kantene og // reverse edges langs banen for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow rGraph[v][u] += path_flow } // Returner den totale flyten retur max_flow; } // Driverprogram for å teste funksjonene ovenfor int main() { // La oss lage en graf vist i eksemplet ovenfor 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; }> |
>
>
Java
// 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) { // Hvis vi finner en forbindelse til sink //-noden, så er det ikke noe poeng i BFS // lenger. Vi må bare sette den overordnede // og kan returnere true if (v == t) { parent[ v] = u; return true; } kø.add(v); forelder[v] = u; besøkt[v] = sant; } } } // Vi nådde ikke synke i BFS fra kilden, // så returner falsk return false; } // Returnerer maksimal flyt fra s til t i den gitte // grafen int fordFulkerson(int graf[][], int s, int t) { int u, v; // Lag en restgraf og fyll restgrafen // grafen med gitte kapasiteter i den opprinnelige grafen // som restkapasiteter i restgrafen // Residualgrafen der rGraph[i][j] indikerer // restkapasiteten til kanten fra i til j (hvis det // er en kant. Hvis rGraph[i][j] er 0, så er det // ikke) int rGraph[][] = new int[V][V]; for (u = 0; u for (v = 0; v rGraph[u][v] = graf[u][v]; // Denne matrisen fylles av BFS og for å lagre bane int parent[] = new int[ V]; int max_flow = 0; // Det er ingen flyt innledningsvis av kantene // langs banen fylt av BFS. Eller vi kan si // finne den maksimale flyten som er funnet int path_flow = Integer.MAX_VALUE for (v = t; v = parent[v ]) { u = parent[v]; path_flow = Math.min(path_flow, rGraph[u][v] } // oppdater restkapasiteten til kantene og // reverse edges langs banen for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; flow max_flow += path_flow; } // Returner den generelle flyten return max_flow; i eksemplet ovenfor int graf[][] = ny 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('Maksimalt mulig flyt er ' + m.fordFulkerson(graf, 0, 5)); } }> |
>
>
Python
# 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) { // Hvis vi finner en forbindelse til sink //-noden, så er det ikke noe poeng i BFS // lenger. Vi må bare sette den overordnede // og kan returnere true if (v == t) { parent[ v] = u; return true; } kø.push(v); forelder[v] = u; besøkt[v] = sant; } } } // Vi nådde ikke synke i BFS starter // fra kilden, så returner false return false; } // Returnerer maksimal flyt fra s til t i // den gitte graffunksjonen fordFulkerson(graf, s, t) { let u, v; // Lag en restgraf og fyll ut // restgrafen med gitte kapasiteter // i den opprinnelige grafen som gjenværende // kapasiteter i restgrafen // Residualgraf der rGraph[i][j] // indikerer restkapasiteten til kanten / / fra i til j (hvis det er en kant. // Hvis rGraph[i][j] er 0, så er det // ikke) la rGraph = new Array(V); for(u = 0; u { rGraph[u] = ny matrise(V); for(v = 0; v rGraph[u][v] = graf[u][v]; } // Denne matrisen er fylt av BFS og for å lagre bane la parent = new Array(V // Det er ingen flyt først la max_flow = 0 // Øk flyten mens det // er bane fra kilde til synke mens (bfs(rGraph, s, t); , parent)) { // Finn minimum restkapasitet til kantene // langs banen fylt av BFS. Eller vi kan si // finne den maksimale flyten gjennom banen som er funnet = Number.MAX_VALUE; ; v != s; v = overordnet[v]) { u = overordnet[v]; omvendte kanter langs banen for(v = t; v != s; v = overordnet[v]) { u = overordnet[v]; = path_flow; } // Legg til baneflyt til overordnet flyt 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('Maksimalt mulig flyt er ' + fordFulkerson(graf, 0, 5)); // Denne koden er bidratt med avanitrachhadiya2155> |
hvordan vite om noen blokkerte deg på Android
>
>Produksjon
The maximum possible flow is 23>
Tidskompleksitet: O(|V| * E^2) , hvor E er antall kanter og V er antall toppunkter.
Romkompleksitet :O(V) , som vi opprettet kø.
Implementeringen ovenfor av Ford Fulkerson Algorithm kalles Edmonds-Karp algoritme . Ideen til Edmonds-Karp er å bruke BFS i Ford Fulkerson-implementering, da BFS alltid velger en bane med minimum antall kanter. Når BFS brukes, kan den verste tidskompleksiteten reduseres til O(VE2). Implementeringen ovenfor bruker tilstøtende matriserepresentasjon selv om BFS tar O(V2) tid, er tidskompleksiteten til implementeringen ovenfor O(EV3) (Se CLRS bok for bevis på tidskompleksitet)
Dette er et viktig problem da det oppstår i mange praktiske situasjoner. Eksempler inkluderer maksimering av transporten med gitte trafikkgrenser, maksimering av pakkeflyt i datanettverk.
Dincs algoritme for Max-Flow.
Trening:
Endre implementeringen ovenfor slik at den kjører i O(VE2) tid.