Šioje pamokoje sužinosite, kas yra „Ford-Fulkerson“ algoritmas. Taip pat rasite darbinių pavyzdžių, kaip surasti maksimalų srautą srauto tinkle C, C ++, Java ir Python.
„Ford-Fulkerson“ algoritmas yra godus būdas apskaičiuoti maksimalų galimą srautą tinkle ar grafike.
Terminas „ srauto tinklas“ naudojamas apibūdinti viršūnių ir kraštų tinklą su šaltiniu (S) ir kriaukle (T). Kiekviena viršūnė, išskyrus S ir T , gali per ją gauti ir išsiųsti vienodą kiekį daiktų. S gali siųsti tik T, o T - tik daiktus.
Mes galime vizualizuoti algoritmo supratimą, naudodami skysčio srautą skirtingos talpos vamzdžių tinkle. Kiekvienas vamzdis turi tam tikrą skysčio talpą, kurį jis gali perduoti pavyzdyje. Šiam algoritmui nustatysime, kiek skysčio galima ištekėti iš šaltinio į kriauklę instancijoje, naudojant tinklą.
Srauto tinklo diagrama
Naudojamos terminijos
Didinimo kelias
Tai kelias, galimas srauto tinkle.
Liekamasis grafikas
Tai reiškia srauto tinklą, kuris turi papildomą galimą srautą.
Liekamasis pajėgumas
Tai yra krašto talpa, atėmus srautą iš didžiausio pajėgumo.
Kaip veikia „Ford-Fulkerson“ algoritmas?
Algoritmas yra toks:
- Inicializuokite srautą visuose kraštuose iki 0.
- Nors tarp šaltinio ir kriauklės yra padidinimo kelias, pridėkite šį kelią prie srauto.
- Atnaujinkite liekamąjį grafiką.
Jei reikia, galime apsvarstyti ir atvirkštinį kelią, nes jei jų neatsižvelgsime, niekada negalėsime rasti maksimalaus srauto.
Aukščiau pateiktas sąvokas galima suprasti pateikiant žemiau pateiktą pavyzdį.
„Ford-Fulkerson“ pavyzdys
Visų kraštų srautas pradžioje yra 0.
Srauto tinklo diagramos pavyzdys
- Pasirinkite bet kurį savavališką kelią nuo S iki T. Šiame žingsnyje mes pasirinkome kelią SABT.
Raskite kelią
Minimali talpa tarp trijų briaunų yra 2 (BT). Atsižvelgdami į tai, atnaujinkite kiekvieno kelio srautą / talpą.
Atnaujinkite pajėgumus - Pasirinkite kitą kelią SDCT. Mažiausias pajėgumas tarp šių kraštų yra 3 (SD).
Raskite kitą kelią Pagal tai
atnaujinkite pajėgumus.
Atnaujinkite pajėgumus - Dabar apsvarstykime ir atvirkštinio kelio BD. Pasirenkamas kelias SABDCT. Mažiausias likutis tarp kraštų yra 1 (DC).
Raskite kitą kelią
. Pajėgumų atnaujinimas.
Atnaujinkite pajėgumus
Pirmyn ir atgal važiuojančių kelių pajėgumas yra nagrinėjamas atskirai. - Pridedant visus srautus = 2 + 3 + 1 = 6, tai yra didžiausias galimas srautas srauto tinkle.
Atkreipkite dėmesį, kad jei bet kurio krašto talpa yra pilna, tada to kelio naudoti negalima.
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
„Python Java C C ++“ # Ford-Fulkerson algorith in Python from collections import defaultdict class Graph: def __init__(self, graph): self.graph = graph self. ROW = len(graph) # Using BFS as a searching algorithm def searching_algo_BFS(self, s, t, parent): visited = (False) * (self.ROW) queue = () queue.append(s) visited(s) = True while queue: u = queue.pop(0) for ind, val in enumerate(self.graph(u)): if visited(ind) == False and val> 0: queue.append(ind) visited(ind) = True parent(ind) = u return True if visited(t) else False # Applying fordfulkerson algorithm def ford_fulkerson(self, source, sink): parent = (-1) * (self.ROW) max_flow = 0 while self.searching_algo_BFS(source, sink, parent): path_flow = float("Inf") s = sink while(s != source): path_flow = min(path_flow, self.graph(parent(s))(s)) s = parent(s) # Adding the path flows max_flow += path_flow # Updating the residual values of edges 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 graph = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)) g = Graph(graph) source = 0 sink = 5 print("Max Flow: %d " % g.ford_fulkerson(source, sink))
// Ford-Fulkerson algorith in Java import java.util.LinkedList; class FordFulkerson ( static final int V = 6; // Using BFS as a searching algorithm boolean bfs(int Graph()(), int s, int t, int p()) ( boolean visited() = new boolean(V); for (int i = 0; i < V; ++i) visited(i) = false; LinkedList queue = new LinkedList(); queue.add(s); visited(s) = true; p(s) = -1; while (queue.size() != 0) ( int u = queue.poll(); for (int v = 0; v 0) ( queue.add(v); p(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph()(), int s, int t) ( int u, v; int Graph()() = new int(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) Graph(u)(v) = graph(u)(v); int p() = new int(V); int max_flow = 0; # Updating the residual calues of edges while (bfs(Graph, s, t, p)) ( int path_flow = Integer.MAX_VALUE; for (v = t; v != s; v = p(v)) ( u = p(v); path_flow = Math.min(path_flow, Graph(u)(v)); ) for (v = t; v != s; v = p(v)) ( u = p(v); Graph(u)(v) -= path_flow; Graph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) public static void main(String() args) throws java.lang.Exception ( int graph()() = new int()() ( ( 0, 8, 0, 0, 3, 0 ), ( 0, 0, 9, 0, 0, 0 ), ( 0, 0, 0, 0, 7, 2 ), ( 0, 0, 0, 0, 0, 5 ), ( 0, 0, 7, 4, 0, 0 ), ( 0, 0, 0, 0, 0, 0 ) ); FordFulkerson m = new FordFulkerson(); System.out.println("Max Flow: " + m.fordFulkerson(graph, 0, 5)); ) )
/ Ford - Fulkerson algorith in C #include #define A 0 #define B 1 #define C 2 #define MAX_NODES 1000 #define O 1000000000 int n; int e; int capacity(MAX_NODES)(MAX_NODES); int flow(MAX_NODES)(MAX_NODES); int color(MAX_NODES); int pred(MAX_NODES); int min(int x, int y) ( return x < y ? x : y; ) int head, tail; int q(MAX_NODES + 2); void enqueue(int x) ( q(tail) = x; tail++; color(x) = B; ) int dequeue() ( int x = q(head); head++; color(x) = C; return x; ) // Using BFS as a searching algorithm int bfs(int start, int target) ( int u, v; for (u = 0; u < n; u++) ( color(u) = A; ) head = tail = 0; enqueue(start); pred(start) = -1; while (head != tail) ( u = dequeue(); for (v = 0; v 0) ( enqueue(v); pred(v) = u; ) ) ) return color(target) == C; ) // Applying fordfulkerson algorithm int fordFulkerson(int source, int sink) ( int i, j, u; int max_flow = 0; for (i = 0; i < n; i++) ( for (j = 0; j = 0; u = pred(u)) ( increment = min(increment, capacity(pred(u))(u) - flow(pred(u))(u)); ) for (u = n - 1; pred(u)>= 0; u = pred(u)) ( flow(pred(u))(u) += increment; flow(u)(pred(u)) -= increment; ) // Adding the path flows max_flow += increment; ) return max_flow; ) int main() ( for (int i = 0; i < n; i++) ( for (int j = 0; j < n; j++) ( capacity(i)(j) = 0; ) ) n = 6; e = 7; capacity(0)(1) = 8; capacity(0)(4) = 3; capacity(1)(2) = 9; capacity(2)(4) = 7; capacity(2)(5) = 2; capacity(3)(5) = 5; capacity(4)(2) = 7; capacity(4)(3) = 4; int s = 0, t = 5; printf("Max Flow: %d", fordFulkerson(s, t)); )
// Ford-Fulkerson algorith in C++ #include #include #include #include using namespace std; #define V 6 // Using BFS as a searching algorithm bool bfs(int rGraph(V)(V), int s, int t, int parent()) ( bool visited(V); memset(visited, 0, sizeof(visited)); queue q; q.push(s); visited(s) = true; parent(s) = -1; while (!q.empty()) ( int u = q.front(); q.pop(); for (int v = 0; v 0) ( q.push(v); parent(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph(V)(V), int s, int t) ( int u, v; int rGraph(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph(u)(v) = graph(u)(v); int parent(V); int max_flow = 0; // Updating the residual values of edges while (bfs(rGraph, s, t, parent)) ( int path_flow = INT_MAX; for (v = t; v != s; v = parent(v)) ( u = parent(v); path_flow = min(path_flow, rGraph(u)(v)); ) for (v = t; v != s; v = parent(v)) ( u = parent(v); rGraph(u)(v) -= path_flow; rGraph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) int main() ( int graph(V)(V) = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)); cout << "Max Flow: " << fordFulkerson(graph, 0, 5) << endl; )
„Ford-Fulkerson“ programos
- Vandens skirstymo vamzdynas
- Dvipusio suderinimo problema
- Tiražas su reikalavimais
