यह दो वर्टेक्स के बीच सबसे छोटे सबसेट पथ या अधिकतम प्रवाह का अर्थ रखने वाले अधिकतम एज-डिस्जॉइंट पथ की संख्या ज्ञात करने के लिए एक C++ प्रोग्राम है।
एल्गोरिदम:
Begin function bfs() returns true if there is path from source s to sink t in the residual graph which indicates additional possible flow in the graph. End Begin function findDisPath() is used to return maximum flow in given graph: A) Initiate flow as 0. B) If there is an augmenting path from source to sink, add the path to flow. C) Return flow. End
उदाहरण कोड
#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
