Ford-Fulkersoni algoritm

Lang L: none (table-of-contents)

Kasutatud terminoloogiad
Kuidas töötab Ford-Fulkersoni algoritm?
Ford-Fulkersoni näide
Pythoni, Java ja C / C ++ näited
Ford-Fulkersoni rakendused

Selles õpetuses saate teada, mis on Ford-Fulkersoni algoritm. Samuti leiate toimivaid näiteid maksimaalse voo leidmiseks voosvõrgus C, C ++, Java ja Python.

Ford-Fulkersoni algoritm on ahne lähenemisviis võrgu või graafiku maksimaalse võimaliku voo arvutamiseks.

Terminit, vooluvõrk , kasutatakse tippude ja servade võrgu kirjeldamiseks koos allikaga (S) ja valamuga (T). Iga tipp, välja arvatud S ja T , saab selle kaudu vastu võtta ja saata võrdse koguse kraami. S saab saata ja T ainult kraami.

Algoritmi mõistmist saame visualiseerida, kasutades vedeliku voogu erineva võimsusega torude võrgus. Igal torul on teatud maht vedelikku, mida ta saab eksemplaris üle kanda. Selle algoritmi jaoks otsime, kui palju vedelikku saab voolata allikast valamu võrku kasutades.

Vooluvõrgu graafik

Kasutatud terminoloogiad

Suurendav tee

See on vooluvõrgus saadaolev tee.

Jääkgraafik

See tähistab voogu, millel on täiendav võimalik voog.

Jääkvõimsus

See on serva läbilaskevõime pärast voolu lahutamist maksimaalsest võimsusest.

Kuidas töötab Ford-Fulkersoni algoritm?

Algoritm on järgmine:

Initsialiseerige voog kõigis servades väärtuseks 0.
Kuigi allika ja valamu vahel on suurendav tee, lisage see tee voolu.
Värskendage jääkgraafikut.

Vajaduse korral võime kaaluda ka pöördteed, sest kui me neid ei arvesta, ei pruugi me kunagi leida maksimaalset voogu.

Ülaltoodud mõisteid saab mõista allpool toodud näite abil.

Ford-Fulkersoni näide

Kõigi servade voog on alguses 0.

Voogvõrgu graafiku näide

Valige suvaline tee S-st T-ni. Selles etapis oleme valinud tee SABT. Tee leidmine
Minimaalne maht kolme serva vahel on 2 (BT). Selle põhjal värskendage iga tee voogu / mahtu. Uuendage võimsusi
Valige mõni muu tee SDCT. Minimaalne maht nende servade vahel on 3 (SD). Järgmise tee leidmine
Uuendage võimsusi vastavalt sellele. Uuendage võimsusi
Mõelgem nüüd ka vastupidise tee BD-le. Tee valimine SABDCT. Minimaalne jääkmaht servade vahel on 1 (DC). Järgmise tee leidmine Võimsuste
värskendamine. Uuendage
läbilaskevõimet Edasi- ja tagasikäigu läbilaskevõimet vaadeldakse eraldi.
Kõigi voogude liitmine = 2 + 3 + 1 = 6, mis on maksimaalne võimalik voog vooluvõrgus.

Pange tähele, et kui mõne serva maht on täis, siis ei saa seda teed kasutada.

Pythoni, Java ja C / C ++ näited

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; )