Ford-Fulkersonův algoritmus je široce používaný algoritmus pro řešení problému maximálního toku v tokové síti. Problém maximálního toku zahrnuje určení maximálního množství toku, které lze poslat ze zdrojového vrcholu do klesajícího vrcholu v orientovaném váženém grafu, s výhradou kapacitních omezení na okrajích.
Algoritmus funguje tak, že iterativně najde rozšiřující cestu, což je cesta od zdroje k jímce v grafu zbytků, tj. grafu získaném odečtením toku proudu od kapacity každé hrany. Algoritmus pak zvýší tok podél této cesty o maximální možnou hodnotu, což je minimální kapacita hran podél cesty.
Problém:
Je dán graf, který představuje síť toků, kde každá hrana má kapacitu. Také vzhledem ke dvěma vrcholům zdroj „s“ a dřez „t“ v grafu najděte maximální možný průtok od s do t s následujícími omezeními:
- Tok na hraně nepřekračuje danou kapacitu hrany.
- Příchozí tok se rovná odchozímu toku pro každý vrchol kromě sat.
Vezměme si například následující graf z knihy CLRS.
linuxové příkazy
Maximální možný průtok ve výše uvedeném grafu je 23.
Doporučený postup Najděte maximální průtok Vyzkoušejte!
Předpoklad : Úvod do problému maximálního průtoku
Ford-Fulkersonův algoritmus
Následuje jednoduchá myšlenka Ford-Fulkersonova algoritmu:
- Začněte s počátečním tokem jako 0.
- Zatímco existuje rozšiřující cesta od zdroje k jímce:
- Najděte rozšiřující cestu pomocí libovolného algoritmu hledání cesty, jako je prohledávání do šířky nebo prohledávání do hloubky.
- Určete množství toku, které lze poslat podél rozšiřující cesty, což je minimální zbytková kapacita podél okrajů cesty.
- Zvyšte průtok podél augmentační dráhy o určené množství.
- Vraťte maximální průtok.
Časová náročnost: Časová složitost výše uvedeného algoritmu je O(max_flow * E). Spustíme smyčku, zatímco existuje rozšiřující cesta. V nejhorším případě můžeme přidat 1 jednotkový tok v každé iteraci. Proto se časová složitost stává O(max_flow * E).
Jak implementovat výše uvedený jednoduchý algoritmus?
Nejprve definujme koncept reziduálního grafu, který je potřebný pro pochopení implementace.
Zbytkový graf průtokové sítě je graf, který ukazuje další možný průtok. Pokud v grafu zbytků existuje cesta od zdroje k propadu, pak je možné přidat průtok. Každá hrana zbytkového grafu má hodnotu tzv zbytková kapacita což se rovná původní kapacitě hrany mínus průtok proudu. Zbytková kapacita je v podstatě aktuální kapacita hrany.
Promluvme si nyní o detailech implementace. Zbytková kapacita je 0, pokud mezi dvěma vrcholy reziduálního grafu není žádná hrana. Můžeme inicializovat zbytkový graf jako původní graf, protože neexistuje žádný počáteční tok a zpočátku se zbytková kapacita rovná původní kapacitě. Abychom našli rozšiřující cestu, můžeme buď provést BFS nebo DFS zbytkového grafu. V níže uvedené implementaci jsme použili BFS. Pomocí BFS můžeme zjistit, zda existuje cesta od zdroje k jímce. BFS také vytváří parent[] pole. Pomocí pole parent[] procházíme nalezenou cestu a najdeme možný průtok touto cestou nalezením minimální zbytkové kapacity podél cesty. Později přidáme tok nalezené cesty k celkovému toku.
Důležité je, že musíme aktualizovat zbytkové kapacity v grafu zbytků. Odečteme tok cesty od všech hran podél cesty a přidáme tok cesty podél reverzních hran Potřebujeme přidat tok cesty podél reverzních hran, protože později může být nutné poslat tok v opačném směru (viz například následující odkaz).
Níže je uvedena implementace Ford-Fulkersonova algoritmu. Aby to bylo jednoduché, graf je reprezentován jako 2D matice.
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) { // Pokud najdeme spojení se sink nodem, // pak už v BFS nemá smysl Musíme // jen nastavit jeho rodiče a můžeme vrátit // true if (v == t) { parent[ v] = u; vrátit true; } q.push(v); rodič[v] = u; navštíveno[v] = true; } } } // Nedosáhli jsme sink v BFS počínaje zdrojem, takže // return false return false; } // Vrátí maximální průtok od s do t v daném grafu int fordFulkerson(int graf[V][V], int s, int t) { int u, v; // Vytvořte reziduální graf a vyplňte reziduální graf // danými kapacitami v původním grafu jako // reziduálními kapacitami v reziduálním grafu int rGraph[V] [V]; // Reziduální graf kde rGraph[i][j] // udává zbytkovou kapacitu hrany // od i do j (pokud tam hrana je. Pokud // rGraph[i][j] je 0, tak není) for (u = 0; u for (v = 0; v rGraph[u][v] = graf[u][v]; int parent[V]; // Toto pole je vyplněno BFS a // ukládá cestu int max_flow = 0 // Na začátku není žádný tok // Rozšiřte tok, když existuje cesta od zdroje k // propadu while (bfs(rGraph, s, t, parent)) { // Najděte minimální zbytkovou kapacitu hran podél // cesty vyplněné BFS Nebo můžeme říci najít // maximální tok nalezenou cestou int cesta_tok = INT_MAX pro (v = t; v != s; v = rodič[v]) { u = parent[v]; cesta_tok = min(cesta_tok, rGraph[u][v] } // aktualizace zbytkových kapacit hran a // obrácení hran podél cesty pro (v = t; v != s; v =); rodič[v]) { u = rodič[v]; rGraph[u][v] -= cesta_tok; // Vrátí celkový tok return max_flow; } // Program ovladače pro testování výše uvedených funkcí int main() { // Vytvořme graf zobrazený ve výše uvedeném příkladu 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; }> |
>
>
Jáva
// 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) { // Pokud najdeme spojení se sink // uzlem, pak už v BFS // není žádný smysl Musíme pouze nastavit jeho rodič // a může vrátit true if (v == t) { parent[ v] = u; vrátit true; } queue.add(v); rodič[v] = u; navštíveno[v] = true; } } } // Nedosáhli jsme sink v BFS počínaje zdrojem, // takže return false return false; } // Vrátí maximální průtok od s do t v daném // grafu int fordFulkerson(int graf[][], int s, int t) { int u, v; // Vytvořte zbytkový graf a vyplňte zbytkový // graf danými kapacitami v původním grafu // jako zbytkové kapacity v grafu zbytků // Zbytkový graf kde rGraph[i][j] označuje // zbytkovou kapacitu hrany od i do j (pokud // je hrana. Je-li rGraph[i][j] 0, pak // není) int rGraph[][] = new int[V][V]; for (u = 0; u for (v = 0; v rGraph[u][v] = graf[u][v]; // Toto pole je vyplněno BFS a pro uložení cesty int parent[] = new int[ V] int max_flow = 0 // Na začátku není žádný tok // Rozšiřte tok, když existuje cesta od zdroje // k propadu while (bfs(rGraph, s, t, parent)) { // Najděte minimální zbytkovou kapacitu; hran // podél cesty vyplněné BFS Nebo můžeme říci // najít maximální průtok nalezenou cestou int cesta_tok = Integer.MAX_VALUE for (v = t; v != s; v = parent[v ]) { u = parent[v]; cesta_tok = Math.min(cesta_tok, rGraph[u][v] } // aktualizace zbytkových kapacit hran a // obrácení hran podél cesty pro (v = t; v != s; v = rodič[v]) { u = rodič[v]; rGraph[u][v] -= tok_cesty[v][u] += tok_cesty } // Přidat tok cesty k celkovému; flow max_flow += path_flow } // Vrátí celkový tok return max_flow } // Ovladač pro testování výše uvedených funkcí public static void main(String[] args) throws java.lang.Exception { // Vytvořme zobrazený graf; ve výše uvedeném příkladu int graf[][] = 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('Maximální možný průtok je ' + m.fordFulkerson(graph, 0, 5)); } }> |
>
>
Krajta
parametr verilog
# 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#
řetězec formátu java
// 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) { // Pokud najdeme spojení se sink // uzlem, pak už v BFS // není žádný smysl Musíme pouze nastavit jeho rodič // a může vrátit true if (v == t) { parent[ v] = u; vrátit true; } fronta.push(v); rodič[v] = u; navštíveno[v] = true; } } } // Nedosáhli jsme sink v BFS počínaje // ze zdroje, takže return false return false; } // Vrátí maximální průtok od s do t v // dané grafové funkci fordFulkerson(graph, s, t) { let u, v; // Vytvořte zbytkový graf a vyplňte // zbytkový graf danými kapacitami // v původním grafu jako zbytkové // kapacity ve zbytkovém grafu // Zbytkový graf kde rGraph[i][j] // označuje zbytkovou kapacitu hrany / / od i do j (pokud existuje hrana. // Pokud je rGraph[i][j] 0, pak je // není) nechť rGraph = new Array(V); for(u = 0; u { rGraph[u] = new Array(V); for(v = 0; v rGraph[u][v] = graph[u][v]; } // Toto pole je vyplněno BFS a pro uložení cesty let parent = new Array(V) // Na začátku není žádný tok let max_flow = 0 // Rozšiřte tok, když // existuje cesta od zdroje k jímce while (bfs(rGraph, s, t); , parent)) { // Najděte minimální zbytkovou kapacitu hran // podél cesty vyplněné BFS Nebo můžeme říci // najít maximální tok nalezenou cestou nech cesta_tok = Číslo.MAX_VALUE; ; v != s; v = rodič[v]) { u = rodič[v]; obrácené hrany podél cesty for(v = t; v != s; v = rodič[v]) { u = rodič[v]] -= tok_cesty[v][u] + = path_flow } // Přidání toku cesty k celkovému toku max_flow += path_flow } // Návrat celkového toku max_flow } // Kód ovladače // Vytvořme graf zobrazený ve výše uvedeném příkladu 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('Maximální možný tok je ' + fordFulkerson(graf, 0, 5)); // Tento kód přispěl avanitrachhadiya2155> |
>
>Výstup
The maximum possible flow is 23>
Časová složitost: O(|V| * E^2) ,kde E je počet hran a V je počet vrcholů.
Prostorová složitost :O(V), jak jsme vytvořili frontu.
Výše uvedená implementace Ford Fulkerson Algorithm se nazývá Edmonds-Karpův algoritmus . Myšlenka Edmonds-Karpa je použít BFS v implementaci Ford Fulkerson, protože BFS vždy vybírá cestu s minimálním počtem hran. Při použití BFS lze časovou složitost v nejhorším případě snížit na O(VE2). Výše uvedená implementace používá reprezentaci matice sousedství, ačkoli BFS bere O(V2) čas, časová složitost výše uvedené implementace je O(EV3) (Odkaz kniha CLRS pro důkaz časové náročnosti)
Toto je důležitý problém, který se objevuje v mnoha praktických situacích. Příklady zahrnují maximalizaci přepravy s danými provozními limity, maximalizaci toku paketů v počítačových sítích.
Dincův algoritmus pro Max-Flow.
Cvičení:
Upravte výše uvedenou implementaci tak, aby běžela v O(VE2) čas.