Ford-Fulkersonov algoritmus

V tomto výučbe sa dozviete, čo je Ford-Fulkersonov algoritmus. Nájdete tiež pracovné príklady hľadania maximálneho prietoku v prietokovej sieti v jazykoch C, C ++, Java a Python.

Algoritmus Ford-Fulkerson je chamtivý prístup k výpočtu maximálneho možného toku v sieti alebo grafe.

Pojmom prietoková sieť sa označuje sieť vrcholov a hrán so zdrojom (S) a ponorom (T). Každý vrchol, okrem S a T , môže cez neho prijímať a posielať rovnaké množstvo vecí. S môže iba odosielať a T iba prijímať veci.

Pochopenie algoritmu môžeme vizualizovať pomocou toku kvapaliny v sieti potrubí rôznych kapacít. Každá rúrka má určitú kapacitu kvapaliny, ktorú môže prenášať v danom okamihu. Pre tento algoritmus zistíme, koľko kvapaliny môže pretekať zo zdroja do výlevky v inštancii pomocou siete.

Graf sieťového toku

Použité terminológie

Zvyšujúca sa cesta

Je to cesta dostupná v prietokovej sieti.

Zvyškový graf

Predstavuje sieť toku, ktorá má ďalší možný tok.

Zostatková kapacita

Je to kapacita okraja po odčítaní prietoku od maximálnej kapacity.

Ako funguje Ford-Fulkersonov algoritmus?

Algoritmus je nasledovný:

  1. Inicializujte tok na všetkých okrajoch na 0.
  2. Aj keď medzi zdrojom a drezom existuje rozširujúca sa cesta, pridajte túto cestu k toku.
  3. Aktualizujte zvyškový graf.

Ak je to potrebné, môžeme zvážiť aj reverznú cestu, pretože ak ich nezohľadníme, možno nikdy nenájdeme maximálny prietok.

Vyššie uvedené pojmy je možné pochopiť na príklade nižšie.

Príklad Ford-Fulkerson

Tok všetkých hrán je na začiatku 0.

Príklad sieťového grafu toku
  1. Vyberte ľubovoľnú cestu od S po T. V tomto kroku sme vybrali cestu SABT. Nájsť cestu
    Minimálna kapacita medzi tromi okrajmi je 2 (BT). Na základe toho aktualizujte tok / kapacitu pre každú cestu. Aktualizujte kapacity
  2. Vyberte inú cestu SDCT. Minimálna kapacita medzi týmito okrajmi je 3 (SD). Nájsť ďalšiu cestu Podľa toho
    aktualizujte kapacity. Aktualizujte kapacity
  3. Uvažujme teraz aj o reverznej ceste BD. Voľba cesty SABDCT. Minimálna zvyšková kapacita medzi okrajmi je 1 (ss). Nájdite ďalšiu cestu
    Aktualizácia kapacít. Aktualizácia kapacít
    Kapacita pre cestu vpred a vzad sa posudzuje osobitne.
  4. Sčítanie všetkých prietokov = 2 + 3 + 1 = 6, čo je maximálny možný prietok v prietokovej sieti.

Upozorňujeme, že ak je kapacita ľubovoľného okraja plná, túto cestu nie je možné použiť.

Príklady jazyka Python, Java a 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; )

Aplikácie Ford-Fulkerson

  • Rozvod vody
  • Problém dvojstrannej zhody
  • Náklad s požiadavkami

Zaujímavé články...