În acest tutorial, veți afla ce este algoritmul Ford-Fulkerson. De asemenea, veți găsi exemple de lucru pentru găsirea debitului maxim într-o rețea de flux în C, C ++, Java și Python.
Algoritmul Ford-Fulkerson este o abordare lacomă pentru calcularea debitului maxim posibil într-o rețea sau un grafic.
Un termen, rețea de flux , este utilizat pentru a descrie o rețea de vârfuri și margini cu o sursă (S) și o chiuvetă (T). Fiecare vârf, cu excepția S și T , poate primi și trimite prin el o cantitate egală de lucruri. S poate trimite numai și T poate primi doar lucruri.
Putem vizualiza înțelegerea algoritmului folosind un flux de lichid în interiorul unei rețele de conducte de diferite capacități. Fiecare țeavă are o anumită capacitate de lichid pe care o poate transfera la o instanță. Pentru acest algoritm, vom găsi cât de mult lichid poate fi curgat de la sursă la chiuvetă la o instanță care utilizează rețeaua.
Graficul rețelei de flux
Terminologiile utilizate
Calea măririi
Este calea disponibilă într-o rețea de flux.
Grafic rezidual
Reprezintă rețeaua de flux care are un flux suplimentar posibil.
Capacitate reziduală
Este capacitatea muchiei după scăderea fluxului din capacitatea maximă.
Cum funcționează algoritmul Ford-Fulkerson?
Urmează algoritmul:
- Inițializați fluxul în toate marginile la 0.
- Deși există o cale de mărire între sursă și chiuvetă, adăugați această cale la flux.
- Actualizați graficul rezidual.
De asemenea, putem lua în considerare calea inversă, dacă este necesar, deoarece dacă nu le luăm în considerare, este posibil să nu găsim niciodată un flux maxim.
Conceptele de mai sus pot fi înțelese cu exemplul de mai jos.
Exemplu Ford-Fulkerson
Fluxul tuturor muchiilor este 0 la început.
Exemplu de grafic de rețea de flux
- Selectați orice cale arbitrară de la S la T. În acest pas, am selectat calea SABT.
Găsiți o cale
Capacitatea minimă dintre cele trei margini este 2 (BT). Pe baza acestui lucru, actualizați fluxul / capacitatea pentru fiecare cale.
Actualizați capacitățile - Selectați o altă cale SDCT. Capacitatea minimă dintre aceste margini este de 3 (SD).
Găsiți calea următoare
Actualizați capacitățile în funcție de aceasta.
Actualizați capacitățile - Acum, să luăm în considerare și BD cu cale inversă. Selectarea căii SABDCT. Capacitatea reziduală minimă dintre margini este 1 (DC).
Găsiți calea următoare
Actualizarea capacităților.
Actualizați capacitățile
Capacitatea pentru căile înainte și inversă sunt considerate separat. - Adăugarea tuturor fluxurilor = 2 + 3 + 1 = 6, care este debitul maxim posibil pe rețeaua de flux.
Rețineți că, dacă capacitatea pentru orice margine este plină, atunci calea respectivă nu poate fi utilizată.
Exemple Python, Java și C / C ++
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; )
Aplicații Ford-Fulkerson
- Conductă de distribuție a apei
- Problemă de potrivire bipartită
- Circulație cu cerințe
