Ford-Fulkerson-algoritm

Innehållsförteckning

Terminologier används
Hur fungerar Ford-Fulkerson algoritm?
Ford-Fulkerson Exempel
Python, Java och C / C ++ exempel
Ford-Fulkerson-applikationer

I denna handledning lär du dig vad Ford-Fulkerson-algoritm är. Du hittar också arbetsexempel för att hitta maximalt flöde i ett flödesnätverk i C, C ++, Java och Python.

Ford-Fulkerson-algoritmen är en girig metod för att beräkna maximalt möjligt flöde i ett nätverk eller en graf.

En term, flödesnätverk , används för att beskriva ett nätverk av hörn och kanter med en källa (S) och ett handfat (T). Varje toppunkt, förutom S och T , kan ta emot och skicka lika mycket grejer genom det. S kan bara skicka och T kan bara ta emot saker.

Vi kan visualisera förståelsen för algoritmen med hjälp av ett vätskeflöde i ett nätverk av rör med olika kapacitet. Varje rör har en viss vätskekapacitet som det kan överföra vid en instans. För denna algoritm ska vi hitta hur mycket vätska som kan strömma från källan till diskbänken vid en instans som använder nätverket.

Flödesnätverksdiagram

Terminologier används

Ökad väg

Det är den sökväg som finns i ett flödesnätverk.

Restdiagram

Det representerar flödesnätverket som har ytterligare möjligt flöde.

Restkapacitet

Det är kantens kapacitet efter att ha dragit från flödet från den maximala kapaciteten.

Hur fungerar Ford-Fulkerson algoritm?

Algoritmen följer:

Initiera flödet i alla kanter till 0.
Medan det finns en förstärkningsväg mellan källan och diskbänken, lägg till den här vägen till flödet.
Uppdatera restdiagrammet.

Vi kan också överväga omvänd väg om det behövs, för om vi inte överväger dem kanske vi aldrig hittar ett maximalt flöde.

Ovanstående begrepp kan förstås med exemplet nedan.

Ford-Fulkerson Exempel

Flödet av alla kanter är 0 i början.

Exempel på flöde nätverksdiagram

Välj valfri väg från S till T. I det här steget har vi valt sökvägen SABT. Hitta en väg
Minsta kapacitet mellan de tre kanterna är 2 (BT). Baserat på detta uppdaterar du flödet / kapaciteten för varje sökväg. Uppdatera kapaciteterna
Välj en annan sökväg SDCT. Minsta kapacitet mellan dessa kanter är 3 (SD). Hitta nästa väg
Uppdatera kapaciteterna enligt detta. Uppdatera kapaciteterna
Låt oss nu också överväga den omvända vägen BD. Välja sökväg SABDCT. Minsta restkapacitet mellan kanterna är 1 (DC). Hitta nästa väg
Uppdatera kapaciteterna. Uppdatera kapaciteterna
Kapaciteten för fram- och bakåtvägar betraktas separat.
Lägga till alla flöden = 2 + 3 + 1 = 6, vilket är maximalt möjligt flöde i flödesnätet.

Observera att om kapaciteten för någon kant är full kan den sökvägen inte användas.

Python, Java och C / C ++ exempel

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