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.

```
/*
```

 * C++ Program to Find Maximum Number of Edge Disjoint Paths

```
 */
```
```
#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();
```
```
}
```

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

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

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

« Prev - C++ Program to Implement Euler Circuit Problem

» Next - C++ Program to Implement Edmonds Karp Algorithm

Related Posts:

Recommended Articles: