यह सोर्स और सिंक वर्टेक्स के बीच अधिकतम प्रवाह की गणना करने के लिए एडमंड्स-कार्प एल्गोरिदम को इम्प्लीमेंट करने के लिए एक C++ प्रोग्राम है।
एल्गोरिदम:
Begin function edmondsKarp() : फ्लो को 0 के रूप में इनिशियलाइज़ करें। यदि सोर्स से सिंक तक एक ऑगमेंटिंग पथ है, तो पथ को फ्लो में जोड़ें। फ्लो लौटाएं। End
उदाहरण कोड
#include<cstdio> #include<queue> #include<cstring> #include<vector> #include<iostream> using namespace std; int c[10][10]; int flowPassed[10][10]; vector<int> g[10]; int parList[10]; int currentPathC[10]; int bfs(int sNode, int eNode)//ब्रेडथ फर्स्ट सर्च { memset(parList, -1, sizeof(parList)); memset(currentPathC, 0, sizeof(currentPathC)); queue<int> q;//क्यू वेक्टर घोषित करें q.push(sNode); parList[sNode] = -1;//parlist के सोर्स नोड को इनिशियलाइज़ करें currentPathC[sNode] = 999;//currentpath के सोर्स नोड को इनिशियलाइज़ करें while(!q.empty())// यदि q खाली नहीं है { int currNode = q.front(); q.pop(); for(int i=0; i<g[currNode].size(); i++) { int to = g[currNode][i]; if(parList[to] == -1) { if(c[currNode][to] - flowPassed[currNode][to] > 0) { parList[to] = currNode; currentPathC[to] = min(currentPathC[currNode], c[currNode][to] - flowPassed[currNode][to]); if(to == eNode) { return currentPathC[eNode]; } q.push(to); } } } } return 0; } int edmondsKarp(int sNode, int eNode) { int maxFlow = 0; while(true) { int flow = bfs(sNode, eNode); if (flow == 0) { break; } maxFlow += flow; int currNode = eNode; while(currNode != sNode) { int prevNode = parList[currNode]; flowPassed[prevNode][currNode] += flow; flowPassed[currNode][prevNode] -= flow; currNode = prevNode; } } return maxFlow; } int main() { int nodCount, edCount; cout<<"enter the number of nodes and edges\n"; cin>>nodCount>>edCount; int source, sink; cout<<"enter the source and sink\n"; cin>>source>>sink; for(int ed = 0; ed < edCount; ed++) { cout<<"enter the start and end vertex along with capacity\n"; int from, to, cap; cin>>from>>to>>cap; c[from][to] = cap; g[from].push_back(to); g[to].push_back(from); } int maxFlow = edmondsKarp(source, sink); cout<<endl<<endl<<"Max Flow is:"<<maxFlow<<endl; }
आउटपुट
enter the number of nodes and edges 6 7 enter the source and sink 0 4 enter the start and end vertex along with capacity 0 1 14 enter the start and end vertex along with capacity 2 4 10 enter the start and end vertex along with capacity 6 7 9 enter the start and end vertex along with capacity 5 2 10 enter the start and end vertex along with capacity 1 4 12 enter the start and end vertex along with capacity 2 0 15 enter the start and end vertex along with capacity 5 3 15 Max Flow is:12
