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. }

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

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

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

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn