Ford-Fulkerson एल्गोरिथ्म

विषय - सूची

प्रयुक्त शब्दावली
Ford-Fulkerson Algorithm कैसे काम करता है?
Ford-Fulkerson उदाहरण
पायथन, जावा और सी / सी ++ उदाहरण
Ford-Fulkerson एप्लीकेशन

इस ट्यूटोरियल में, आप सीखेंगे कि Ford-Fulkerson एल्गोरिथ्म क्या है। साथ ही, आपको C, C ++, Java और पायथन में एक प्रवाह नेटवर्क में अधिकतम प्रवाह खोजने के काम के उदाहरण मिलेंगे।

Ford-Fulkerson एल्गोरिथ्म एक नेटवर्क या ग्राफ़ में अधिकतम संभव प्रवाह की गणना के लिए एक लालची दृष्टिकोण है।

एक शब्द, प्रवाह नेटवर्क , एक स्रोत (एस) और एक सिंक (टी) के साथ कोने और किनारों के नेटवर्क का वर्णन करने के लिए उपयोग किया जाता है। प्रत्येक शीर्ष, एस और टी को छोड़कर, इसके माध्यम से सामान की एक समान मात्रा प्राप्त और भेज सकता है। S केवल भेज सकता है और T केवल सामान प्राप्त कर सकता है।

हम विभिन्न क्षमताओं के पाइप के नेटवर्क के अंदर तरल के प्रवाह का उपयोग करके एल्गोरिथ्म की समझ की कल्पना कर सकते हैं। प्रत्येक पाइप में तरल की एक निश्चित क्षमता होती है जो एक उदाहरण पर स्थानांतरित कर सकता है। इस एल्गोरिथ्म के लिए, हम यह पता लगाने जा रहे हैं कि नेटवर्क का उपयोग करके एक उदाहरण पर स्रोत से सिंक तक कितना तरल प्रवाहित किया जा सकता है।

प्रवाह नेटवर्क ग्राफ

प्रयुक्त शब्दावली

पथ का पथ

यह प्रवाह नेटवर्क में उपलब्ध पथ है।

अवशिष्ट ग्राफ

यह प्रवाह नेटवर्क का प्रतिनिधित्व करता है जिसमें अतिरिक्त संभव प्रवाह होता है।

अवशिष्ट क्षमता

यह अधिकतम क्षमता से प्रवाह को घटाने के बाद किनारे की क्षमता है।

Ford-Fulkerson Algorithm कैसे काम करता है?

एल्गोरिथ्म इस प्रकार है:

सभी किनारों में प्रवाह को प्रारंभिक ०।
जबकि स्रोत और सिंक के बीच एक उन्नत पथ है, इस पथ को प्रवाह में जोड़ें।
अवशिष्ट ग्राफ को अपडेट करें।

आवश्यकता पड़ने पर हम रिवर्स-पाथ पर भी विचार कर सकते हैं क्योंकि यदि हम उन पर विचार नहीं करते हैं, तो हमें कभी भी अधिकतम प्रवाह नहीं मिल सकता है।

उपरोक्त अवधारणाओं को नीचे दिए गए उदाहरण से समझा जा सकता है।

Ford-Fulkerson उदाहरण

शुरुआत में सभी किनारों का प्रवाह 0 है।

प्रवाह नेटवर्क ग्राफ उदाहरण

S से T तक किसी भी मनमाने रास्ते का चयन करें। इस चरण में, हमने पथ SABT को चुना है। पथ खोजें
तीनों किनारों के बीच की न्यूनतम क्षमता 2 (बीटी) है। इसके आधार पर, प्रत्येक पथ के लिए प्रवाह / क्षमता को अपडेट करें। क्षमताओं को अपडेट करें
एक और रास्ता चुनें SDCT। इन किनारों के बीच न्यूनतम क्षमता 3 (एसडी) है। अगला रास्ता खोजें इसके
अनुसार क्षमताओं को अपडेट करें। क्षमताओं को अपडेट करें
अब, हम रिवर्स पथ बीडी पर भी विचार करते हैं। पथ का चयन SABDCT किनारों के बीच न्यूनतम अवशिष्ट क्षमता 1 (डीसी) है। अगला रास्ता खोजें
क्षमताओं का अद्यतन करना। क्षमताओं को अपडेट करें
आगे और रिवर्स पथ के लिए क्षमता को अलग-अलग माना जाता है।
सभी प्रवाह जोड़ना = 2 + 3 + 1 = 6, जो प्रवाह नेटवर्क पर अधिकतम संभव प्रवाह है।

ध्यान दें कि यदि किसी किनारे के लिए क्षमता भरी है, तो उस पथ का उपयोग नहीं किया जा सकता है।

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++

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