এটি একটি সি++ প্রোগ্রাম যা এডমন্ডস-কার্প অ্যালগরিদম (Edmonds-Karp algorithm) বাস্তবায়ন করে সোর্স (source) এবং সিংক (sink) ভের্টেক্সের মধ্যে ম্যাক্সিমাম ফ্লো (maximum flow) ক্যালকুলেট করতে।
অ্যালগরিদম:
শুরু ফাংশন edmondsKarp() : ফ্লো (flow) ০ হিসেবে ইনিশিয়ালাইজ করুন। যদি সোর্স থেকে সিংক-এ একটি অগমেন্টিং পাথ (augmenting path) থাকে, তবে পাথটিকে ফ্লোতে যোগ করুন। ফ্লো রিটার্ন করুন। শেষ
উদাহরণ কোড
#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)//ব্রেডথ ফার্স্ট সার্চ (BFS) { memset(parList, -1, sizeof(parList)); memset(currentPathC, 0, sizeof(currentPathC)); queue<int> q;//কিউ ভেক্টর ডিক্লেয়ার q.push(sNode); parList[sNode] = -1;//parList-এর সোর্স নোড ইনিশিয়ালাইজ currentPathC[sNode] = 999;//currentPathC-এর সোর্স নোড ইনিশিয়ালাইজ 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<<"নোড এবং এজের সংখ্যা লিখুন\n"; cin>>nodCount>>edCount; int source, sink; cout<<"সোর্স এবং সিংক লিখুন\n"; cin>>source>>sink; for(int ed = 0; ed < edCount; ed++) { cout<<"শুরুর এবং শেষ ভের্টেক্স ক্যাপাসিটির সাথে লিখুন\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; }
আউটপুট
নোড এবং এজের সংখ্যা লিখুন ৬ ৭ সোর্স এবং সিংক লিখুন ০ ৪ শুরুর এবং শেষ ভের্টেক্স ক্যাপাসিটির সাথে লিখুন ০ ১ ১৪ শুরুর এবং শেষ ভের্টেক্স ক্যাপাসিটির সাথে লিখুন ২ ৪ ১০ শুরুর এবং শেষ ভের্টেক্স ক্যাপাসিটির সাথে লিখুন ৬ ৭ ৯ শুরুর এবং শেষ ভের্টেক্স ক্যাপাসিটির সাথে লিখুন ৫ ২ ১০ শুরুর এবং শেষ ভের্টেক্স ক্যাপাসিটির সাথে লিখুন ১ ৪ ১২ শুরুর এবং শেষ ভের্টেক্স ক্যাপাসিটির সাথে লিখুন ২ ০ ১৫ শুরুর এবং শেষ ভের্টেক্স ক্যাপাসিটির সাথে লিখুন ৫ ৩ ১৫ Max Flow is:12
