C++ 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.
This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

  1. /*
  2.  * C++ Program to Find Maximum Number of Edge Disjoint Paths
  3.  */
  4. #include <iostream>
  5. #include <limits.h>
  6. #include <string.h>
  7. #include <queue>
  8. #include<conio.h>
  9. using namespace std;
  10. #define V 8
  11.  
  12. bool bfs(int rGraph[V][V], int s, int t, int parent[])
  13. {
  14.     bool visited[V];
  15.     memset(visited, 0, sizeof(visited)); 
  16.     queue <int> q;
  17.     q.push(s);
  18.     visited[s] = true;
  19.     parent[s] = -1;
  20.     while (!q.empty())
  21.     {
  22.         int u = q.front();
  23.         q.pop();
  24.         for (int v = 0; v < V; v++)
  25.         {
  26.             if (visited[v] == false && rGraph[u][v] > 0)
  27.             {
  28.                 q.push(v);
  29.                 parent[v] = u;
  30.                 visited[v] = true;
  31.             }
  32.         }
  33.     }
  34.     return (visited[t] == true);
  35. }
  36. int findDisjointPaths(int graph[V][V], int s, int t)
  37. {
  38.     int u, v;
  39.     int rGraph[V][V];
  40.     for (u = 0; u < V; u++)
  41.         for (v = 0; v < V; v++)
  42.         {
  43.              rGraph[u][v] = graph[u][v];
  44.         }
  45.     }
  46.     int parent[V];
  47.     int max_flow = 0;
  48.     while (bfs(rGraph, s, t, parent))
  49.     {
  50.         int path_flow = INT_MAX;
  51.         for (v = t; v != s; v = parent[v])
  52.         {
  53.             u = parent[v];
  54.             path_flow = min(path_flow, rGraph[u][v]);
  55.         }
  56.         for (v = t; v != s; v = parent[v])
  57.         {
  58.             u = parent[v];
  59.             rGraph[u][v] -= path_flow;
  60.             rGraph[v][u] += path_flow;
  61.         }
  62.         max_flow += path_flow;
  63.     }
  64.     return max_flow;
  65. }
  66. int main()
  67. {
  68.     int graph[V][V] = { {0, 1, 1, 1, 0, 0, 0, 0},
  69.                         {0, 0, 1, 0, 0, 0, 0, 0},
  70.                         {0, 0, 0, 1, 0, 0, 1, 0},
  71.                         {0, 0, 0, 0, 0, 0, 1, 0},
  72.                         {0, 0, 1, 0, 0, 0, 0, 1},
  73.                         {0, 1, 0, 0, 0, 0, 0, 1},
  74.                         {0, 0, 0, 0, 0, 1, 0, 1},
  75.                         {0, 0, 0, 0, 0, 0, 0, 0}
  76.                       };
  77.  
  78.     int s = 0;
  79.     int t = 7;
  80.     cout << "There can be maximum " << findDisjointPaths(graph, s, t)<< " edge-disjoint paths from " << s <<" to "<<t;
  81.     getch();
  82. }

Output
There can be maximum 2 edge-disjoint paths from 0 to 7

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.