এটি একটি সি++ প্রোগ্রাম যা সর্বোচ্চ এজ-ডিসজয়েন্ট পাথ (Maximum Number of Edge Disjoint Paths) বের করে, যার অর্থ হল দুটি ভের্টেক্সের মধ্যে শর্টেস্ট সাবসেট পাথ বা ম্যাক্সিমাম ফ্লো (maximum flow)।
অ্যালগরিদম:
শুরু ফাংশন bfs() রিটার্ন করে true যদি রেসিডুয়াল গ্রাফে সোর্স s থেকে সিংক t-এ পথ থাকে যা গ্রাফে অতিরিক্ত সম্ভাব্য ফ্লো নির্দেশ করে। শেষ শুরু ফাংশন findDisPath() দেয়া গ্রাফে ম্যাক্সিমাম ফ্লো রিটার্ন করতে ব্যবহৃত হয়: ক) ফ্লো ০ হিসেবে ইনিশিয়ালাইজ করুন। খ) যদি সোর্স থেকে সিংক-এ একটি অগমেন্টিং পাথ থাকে, তবে পাথটিকে ফ্লোতে যোগ করুন। গ) ফ্লো রিটার্ন করুন। শেষ
উদাহরণ কোড
#include <iostream> #include <climits> #include <cstring> #include <queue> #define n 7 using namespace std; bool bfs(int g[n][n], int s, int t, int par[]) { bool visit[n]; memset(visit, 0, sizeof(visit)); queue <int> q; q.push(s); visit[s] = true; par[s] = -1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v=0; v<n; v++) { if (visit[v]==false && g[u][v] > 0) { q.push(v); par[v] = u; visit[v] = true; } } } return (visit[t] == true); } int findDisPath(int G[n][n], int s, int t) { int u, v; int g[n][n]; for (u = 0; u < n; u++) { for (v = 0; v < n; v++) g[u][v] = G[u][v]; } int par[n]; int max_flow = 0; while (bfs(g, s, t,par)) { int path_flow = INT_MAX; for (v=t; v!=s; v=par[v]) { u = par[v]; path_flow = min(path_flow, g[u][v]); } for (v = t; v != s; v = par[v]) { u = par[v]; g[u][v] -= path_flow; g[v][u] += path_flow; } max_flow += path_flow; } return max_flow; } int main() { int g[n][n] = {{0, 6, 7, 1}, {0, 0, 4, 2}, {0, 5, 0, 0}, {0, 0, 19, 12}, {0, 0, 0, 17}, {0, 0, 0, 0,}}; int s=0,d=3; cout << " There exist maximum" <<" "<< findDisPath(g, s, d)<< " edgedisjoint paths from " << s <<" to "<<d; return 0; }
আউটপুট
There exist maximum 3 edge-disjoint paths from 0 to 3
