C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Find Maximum Number of Edge Disjoint Paths Program to Find Maximum Number of Edge Disjoint Paths This C++ program displays the maximum number of edge disjoint paths present between two vertices. Maximum number of edge disjoint paths refers to the maximum flow or shortest subset path between two vertices. Here is the source code of the C++ program to display the number of paths present between two given vertices on being given a directed graph as input. #include <iostream> #include <limits.h> #include <string.h> #include <queue> #include<conio.h> using namespace std; #define V 8 bool bfs(int rGraph[V][V], int s, int t, int parent[]) { bool visited[V]; memset(visited, 0, sizeof(visited)); queue <int> q; q.push(s); visited[s] = true; parent[s] = -1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v < V; v++) { if (visited[v] == false && rGraph[u][v] > 0) { q.push(v); parent[v] = u; visited[v] = true; } } } return (visited[t] == true); } int findDisjointPaths(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; 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; } max_flow += path_flow; } return max_flow; } int main() { int graph[V][V] = { {0, 1, 1, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0} }; int s = 0; int t = 7; cout << "There can be maximum " << findDisjointPaths(graph, s, t)<< " edge-disjoint paths from " << s <<" to "<<t; getch(); }