Ford-Fulkerson-algoritmen är en allmänt använd algoritm för att lösa problemet med maximalt flöde i ett flödesnätverk. Det maximala flödesproblemet innebär att bestämma den maximala mängden flöde som kan skickas från en källpunkt till en sjunkpunkt i en riktad viktad graf, med förbehåll för kapacitetsbegränsningar på kanterna.
Algoritmen fungerar genom att iterativt hitta en förstärkningsbana, som är en väg från källan till sänkan i restgrafen, det vill säga grafen som erhålls genom att subtrahera strömflödet från kapaciteten för varje kant. Algoritmen ökar sedan flödet längs denna väg med maximalt möjliga mängd, vilket är den minsta kapaciteten för kanterna längs banan.
Problem:
Givet en graf som representerar ett flödesnätverk där varje kant har en kapacitet. Också med tanke på två hörn källa 's' och handfat 't' i grafen, hitta det maximala möjliga flödet från s till t med följande begränsningar:
- Flödet på en kant överstiger inte kantens givna kapacitet.
- Inkommande flöde är lika med utgående flöde för varje vertex utom s och t.
Tänk till exempel på följande graf från CLRS-boken.
Det maximala möjliga flödet i diagrammet ovan är 23.
jämför med strängRekommenderad praxis Hitta det maximala flödet Prova det!
Förutsättning: Max Flow Problem Introduktion
Ford-Fulkerson Algoritm
Följande är enkel idé om Ford-Fulkerson-algoritmen:
- Börja med initialt flöde som 0.
- Medan det finns en utökad väg från källan till diskbänken:
- Hitta en utökad sökväg med valfri sökvägsalgoritm, till exempel bredd-först-sökning eller djup-först-sökning.
- Bestäm mängden flöde som kan skickas längs förstärkningsbanan, vilket är den minsta restkapaciteten längs banans kanter.
- Öka flödet längs den förstärkande banan med den bestämda mängden.
- Returnera maximalt flöde.
Tidskomplexitet: Tidskomplexiteten för ovanstående algoritm är O(max_flöde * E). Vi kör en slinga medan det finns en förstärkningsbana. I värsta fall kan vi lägga till 1 enhetsflöde i varje iteration. Därför blir tidskomplexiteten O(max_flöde * E).
Hur implementerar man ovanstående enkla algoritm?
Låt oss först definiera begreppet Residual Graph som behövs för att förstå implementeringen.
Restdiagram för ett flödesnätverk är en graf som indikerar ytterligare möjliga flöden. Om det finns en väg från källa till sjunka i restgrafen är det möjligt att lägga till flöde. Varje kant på en restgraf har ett värde som kallas restkapacitet vilket är lika med kantens ursprungliga kapacitet minus strömflöde. Restkapacitet är i princip kantens nuvarande kapacitet.
Låt oss nu prata om implementeringsdetaljer. Restkapaciteten är 0 om det inte finns någon kant mellan två hörn av restgrafen. Vi kan initialisera restgrafen som originalgraf eftersom det inte finns något initialflöde och initialt restkapacitet är lika med ursprunglig kapacitet. För att hitta en förstärkningsväg kan vi antingen göra en BFS eller DFS av restgrafen. Vi har använt BFS i nedanstående implementering. Med hjälp av BFS kan vi ta reda på om det finns en väg från källa till sjunka. BFS bygger också parent[]-array. Med hjälp av parent[]-matrisen går vi genom den hittade banan och hittar möjligt flöde genom denna väg genom att hitta minsta restkapacitet längs banan. Vi lägger senare till det hittade vägflödet till det övergripande flödet.
Det viktiga är att vi måste uppdatera restkapaciteten i restgrafen. Vi subtraherar banflödet från alla kanter längs banan och vi lägger till banflödet längs de omvända kanterna. Vi måste lägga till banflödet längs omvända kanterna eftersom det senare kan behöva skicka flöde i omvänd riktning (se följande länk till exempel).
Nedan är implementeringen av Ford-Fulkerson-algoritmen. För att göra det enkelt representeras grafen som en 2D-matris.
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) { // Om vi hittar en koppling till sinknoden, // så är det ingen mening med BFS längre. Vi // måste bara ställa in dess förälder och kan returnera // true if (v == t) { parent[ v] = u; returnera sant; } q.push(v); förälder[v] = u; besökt[v] = sant; } } } // Vi nådde inte sink i BFS från källan, så // returnerar false return false; } // Returnerar det maximala flödet från s till t i den givna grafen int fordFulkerson(int graph[V][V], int s, int t) { int u, v; // Skapa en restgraf och fyll restgrafen // med givna kapaciteter i den ursprungliga grafen som // restkapaciteter i restgrafen int rGraph[V] [V]; // Restgraf där rGraph[i][j] // indikerar restkapacitet av kanten // från i till j (om det finns en kant. Om // rGraph[i][j] är 0, så finns det inte) for (u = 0; u för (v = 0; v rGraph[u][v] = graf[u][v]; int parent[V]; // Denna matris fylls av BFS och till // lagra sökväg int max_flow = 0; // Det finns inget flöde initialt // Öka flödet medan det finns väg från källan till // sink while (bfs(rGraph, s, t, parent)) { // Hitta minsta restkapacitet för kanterna längs // sökvägen fylld av BFS Eller vi kan säga hitta // maximala flödet genom sökvägen int path_flow = INT_MAX; parent[v]; path_flow = min(path_flow, rGraph[u][v] } // uppdatera restkapaciteten för kanterna och // omvända kanter längs banan för (v = t; v != s; v = förälder[v]) { u = förälder[v]; // Returnera den totala flödesreturen max_flow; } // Drivrutinsprogram för att testa ovanstående funktioner int main() { // Låt oss skapa en graf som visas i exemplet ovan 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) { // Om vi hittar en koppling till sink // noden, så är det ingen mening med BFS // längre. Vi måste bara ställa in dess förälder // och kan returnera true if (v == t) { parent[ v] = u; returnera sant; } queue.add(v); förälder[v] = u; besökt[v] = sant; } } } // Vi nådde inte sink i BFS från källan, // så returnera false return false; } // Returnerar det maximala flödet från s till t i den givna // grafen int fordFulkerson(int graf[][], int s, int t) { int u, v; // Skapa en restgraf och fyll den resterande // grafen med givna kapaciteter i den ursprungliga grafen // som restkapaciteter i restgrafen // Residual graph där rGraph[i][j] indikerar // restkapacitet av kant från i till j (om det // finns en kant. Om rGraph[i][j] är 0, så finns det // inte) int rGraph[][] = new int[V][V]; for (u = 0; u för (v = 0; v rGraph[u][v] = graf[u][v]; // Denna array fylls av BFS och för att lagra sökväg int parent[] = new int[ V]; int max_flow = 0; // Det finns inget flöde initialt // Öka flödet medan det finns väg från källan // till sink while (bfs(rGraph, s, t, parent)) { // Hitta minsta restkapacitet av kanterna // längs vägen som fylls av BFS. Eller vi kan säga // hitta det maximala flödet int path_flow = Integer.MAX_VALUE för (v = t; v != s; v = parent[v ]) { u = parent[v]; path_flow = Math.min(path_flow, rGraph[u][v] } // uppdatera restkapaciteter för kanterna och // omvända kanter längs banan för (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; } // Returnera det övergripande flödet return max_flow } // Drivrutinsprogram för att testa ovanstående funktioner public static void main(String[] args) kastar java.lang.Exception { // Låt oss skapa en graf som visas i exemplet ovan 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('Det maximala möjliga flödet är ' + m.fordFulkerson(graf, 0, 5)); } }> |
>
>
Pytonorm
# 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> |
>
>
huffman kodningskod
C#
java lokaldatum
// 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) { // Om vi hittar en koppling till sink // noden, så är det ingen mening med BFS // längre. Vi måste bara ställa in dess förälder // och kan returnera true if (v == t) { parent[ v] = u; returnera sant; } queue.push(v); förälder[v] = u; besökt[v] = sant; } } } // Vi nådde inte sink i BFS med start // från källan, så returnera false return false; } // Returnerar det maximala flödet från s till t i // den givna graffunktionen fordFulkerson(graf, s, t) { let u, v; // Skapa en restgraf och fyll // restgrafen med givna kapaciteter // i den ursprungliga grafen som resterande // kapaciteter i restgrafen // Residualgraf där rGraph[i][j] // indikerar restkapacitet av kant // / från i till j (om det finns en kant. // Om rGraph[i][j] är 0, så finns det // inte) låt rGraph = new Array(V); for(u = 0; u { rGraph[u] = new Array(V); for(v = 0; v rGraph[u][v] = graph[u][v]; } // Denna array fylls av BFS och för att lagra sökväg låt förälder = new Array(V // Det finns inget flöde initialt låt max_flow = 0 // Öka flödet medan det finns väg från källa till sjunka medan (bfs(rGraph, s, t); , parent)) { // Hitta minsta restkapacitet av kanterna // längs vägen som fylls av BFS. Eller vi kan säga // hitta det maximala flödet genom sökvägen = Number.MAX_VALUE for(v = t ; v != s; v = parent[v]) { u = parent[v]; omvända kanter längs banan för(v = t; v != s; v = förälder[v]) { u = förälder[u][v] -= sökväg[v][u] + = path_flow; } // Lägg till vägflöde till övergripande flöde max_flöde } // Returnera det övergripande flödet retur max_flöde } // Driver code // Låt oss skapa en graf som visas i exemplet ovan , 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('Högsta möjliga flöde är ' + fordFulkerson(graf, 0, 5)); // Denna kod är bidragit av avanitrachhadiya2155> |
>
>Produktion
The maximum possible flow is 23>
Tidskomplexitet: O(|V| * E^2) , där E är antalet kanter och V är antalet hörn.
Rymdkomplexitet :O(V) , när vi skapade kö.
Ovanstående implementering av Ford Fulkerson Algorithm kallas Edmonds-Karps algoritm . Tanken med Edmonds-Karp är att använda BFS i Ford Fulkerson-implementering eftersom BFS alltid väljer en väg med minsta antal kanter. När BFS används kan tidskomplexiteten i värsta fall reduceras till O(VE2). Implementeringen ovan använder dock närliggande matrisrepresentation där BFS tar O(V2) tid, är tidskomplexiteten för ovanstående implementering O(EV3) (Hänvisa CLRS bok för bevis på tidskomplexitet)
Detta är ett viktigt problem eftersom det uppstår i många praktiska situationer. Exempel inkluderar maximering av transporten med givna trafikgränser, maximering av paketflödet i datornätverk.
Dincs algoritm för Max-Flow.
Träning:
Ändra implementeringen ovan så att den körs i O(VE2) tid.