# Find maximum number of edge disjoint paths between two vertices

Given a directed graph and two vertices in it, source ‘s’ and destination ‘t’, find out the maximum number of edge disjoint paths from s to t. Two paths are said edge disjoint if they don’t share any edge.

There can be maximum two edge disjoint paths from source 0 to destination 7 in the above graph. Two edge disjoint paths are highlighted below in red and blue colors are 0-2-6-7 and 0-3-6-5-7.

Note that the paths may be different, but the maximum number is same. For example, in the above diagram, another possible set of paths is 0-1-2-6-7 and 0-3-6-5-7 respectively.

This problem can be solved by reducing it to maximum flow problem. Following are steps.
1) Consider the given source and destination as source and sink in flow network. Assign unit capacity to each edge.
2) Run Ford-Fulkerson algorithm to find the maximum flow from source to sink.
3) The maximum flow is equal to the maximum number of edge-disjoint paths.

When we run Ford-Fulkerson, we reduce the capacity by a unit. Therefore, the edge can not be used again. So the maximum flow is equal to the maximum number of edge-disjoint paths.

Following is C++ implementation of the above algorithm. Most of the code is taken from here.

## C/C++

 `// C++ program to find maximum number of edge disjoint paths ` `#include ` `#include ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `// Number of vertices in given graph ` `#define V 8 ` ` `  `/* Returns true if there is a path from source 's' to sink 't' in ` `  ``residual graph. Also fills parent[] to store the path */` `bool` `bfs(``int` `rGraph[V][V], ``int` `s, ``int` `t, ``int` `parent[]) ` `{ ` `    ``// Create a visited array and mark all vertices as not visited ` `    ``bool` `visited[V]; ` `    ``memset``(visited, 0, ``sizeof``(visited)); ` ` `  `    ``// Create a queue, enqueue source vertex and mark source vertex ` `    ``// as visited ` `    ``queue <``int``> q; ` `    ``q.push(s); ` `    ``visited[s] = ``true``; ` `    ``parent[s] = -1; ` ` `  `    ``// Standard BFS Loop ` `    ``while` `(!q.empty()) ` `    ``{ ` `        ``int` `u = q.front(); ` `        ``q.pop(); ` ` `  `        ``for` `(``int` `v=0; v 0) ` `            ``{ ` `                ``q.push(v); ` `                ``parent[v] = u; ` `                ``visited[v] = ``true``; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// If we reached sink in BFS starting from source, then return ` `    ``// true, else false ` `    ``return` `(visited[t] == ``true``); ` `} ` ` `  `// Returns tne maximum number of edge-disjoint paths from s to t. ` `// This function is copy of forFulkerson() discussed at http://goo.gl/wtQ4Ks ` `int` `findDisjointPaths(``int` `graph[V][V], ``int` `s, ``int` `t) ` `{ ` `    ``int` `u, v; ` ` `  `    ``// Create a residual graph and fill the residual graph with ` `    ``// given capacities in the original graph as residual capacities ` `    ``// in residual graph ` `    ``int` `rGraph[V][V]; ``// Residual graph where rGraph[i][j] indicates ` `                     ``// residual capacity of edge from i to j (if there ` `                     ``// is an edge. If rGraph[i][j] is 0, then there is not) ` `    ``for` `(u = 0; u < V; u++) ` `        ``for` `(v = 0; v < V; v++) ` `             ``rGraph[u][v] = graph[u][v]; ` ` `  `    ``int` `parent[V];  ``// This array is filled by BFS and to store path ` ` `  `    ``int` `max_flow = 0;  ``// There is no flow initially ` ` `  `    ``// Augment the flow while tere is path from source to sink ` `    ``while` `(bfs(rGraph, s, t, parent)) ` `    ``{ ` `        ``// Find minimum residual capacity of the edges along the ` `        ``// path filled by BFS. Or we can say find the maximum flow ` `        ``// through the path found. ` `        ``int` `path_flow = INT_MAX; ` ` `  `        ``for` `(v=t; v!=s; v=parent[v]) ` `        ``{ ` `            ``u = parent[v]; ` `            ``path_flow = min(path_flow, rGraph[u][v]); ` `        ``} ` ` `  `        ``// update residual capacities of the edges and reverse edges ` `        ``// along the path ` `        ``for` `(v=t; v != s; v=parent[v]) ` `        ``{ ` `            ``u = parent[v]; ` `            ``rGraph[u][v] -= path_flow; ` `            ``rGraph[v][u] += path_flow; ` `        ``} ` ` `  `        ``// Add path flow to overall flow ` `        ``max_flow += path_flow; ` `    ``} ` ` `  `    ``// Return the overall flow (max_flow is equal to maximum ` `    ``// number of edge-disjoint paths) ` `    ``return` `max_flow; ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``// Let us create a graph shown in the above example ` `    ``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 ; ` ` `  `    ``return` `0; ` `} `

## Python

 `# Python program to find maximum number of edge disjoint paths ` `# Complexity : (E*(V^3)) ` `# Total augmenting path = VE  ` `# and BFS with adj matrix takes :V^2 times ` `  `  `from` `collections ``import` `defaultdict ` `  `  `#This class represents a directed graph using  ` `# adjacency matrix representation ` `class` `Graph: ` `  `  `    ``def` `__init__(``self``,graph): ` `        ``self``.graph ``=` `graph ``# residual graph ` `        ``self``. ROW ``=` `len``(graph) ` `         `  `  `  `    ``'''Returns true if there is a path from source 's' to sink 't' in ` `    ``residual graph. Also fills parent[] to store the path '''` `    ``def` `BFS(``self``,s, t, parent): ` ` `  `        ``# Mark all the vertices as not visited ` `        ``visited ``=``[``False``]``*``(``self``.ROW) ` `         `  `        ``# Create a queue for BFS ` `        ``queue``=``[] ` `         `  `        ``# Mark the source node as visited and enqueue it ` `        ``queue.append(s) ` `        ``visited[s] ``=` `True` `         `  `        ``# Standard BFS Loop ` `        ``while` `queue: ` ` `  `            ``#Dequeue a vertex from queue and print it ` `            ``u ``=` `queue.pop(``0``) ` `         `  `            ``# Get all adjacent vertices of the dequeued vertex u ` `            ``# If a adjacent has not been visited, then mark it ` `            ``# visited and enqueue it ` `            ``for` `ind, val ``in` `enumerate``(``self``.graph[u]): ` `                ``if` `visited[ind] ``=``=` `False` `and` `val > ``0` `: ` `                    ``queue.append(ind) ` `                    ``visited[ind] ``=` `True` `                    ``parent[ind] ``=` `u ` ` `  `        ``# If we reached sink in BFS starting from source, then return ` `        ``# true, else false ` `        ``return` `True` `if` `visited[t] ``else` `False` `             `  `     `  `    ``# Returns tne maximum number of edge-disjoint paths from  ` `    ``#s to t in the given graph ` `    ``def` `findDisjointPaths(``self``, source, sink): ` ` `  `        ``# This array is filled by BFS and to store path ` `        ``parent ``=` `[``-``1``]``*``(``self``.ROW) ` ` `  `        ``max_flow ``=` `0` `# There is no flow initially ` ` `  `        ``# Augment the flow while there is path from source to sink ` `        ``while` `self``.BFS(source, sink, parent) : ` ` `  `            ``# Find minimum residual capacity of the edges along the ` `            ``# path filled by BFS. Or we can say find the maximum flow ` `            ``# through the path found. ` `            ``path_flow ``=` `float``(``"Inf"``) ` `            ``s ``=` `sink ` `            ``while``(s !``=`  `source): ` `                ``path_flow ``=` `min` `(path_flow, ``self``.graph[parent[s]][s]) ` `                ``s ``=` `parent[s] ` ` `  `            ``# Add path flow to overall flow ` `            ``max_flow ``+``=`  `path_flow ` ` `  `            ``# update residual capacities of the edges and reverse edges ` `            ``# along the path ` `            ``v ``=` `sink ` `            ``while``(v !``=`  `source): ` `                ``u ``=` `parent[v] ` `                ``self``.graph[u][v] ``-``=` `path_flow ` `                ``self``.graph[v][u] ``+``=` `path_flow ` `                ``v ``=` `parent[v] ` ` `  `        ``return` `max_flow ` ` `  `  `  `# Create a graph given in the above diagram ` ` `  `graph ``=` `[[``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``]] ` `  `  ` `  `g ``=` `Graph(graph) ` ` `  `source ``=` `0``; sink ``=` `7` `  `  `print` `(``"There can be maximum %d edge-disjoint paths from %d to %d"` `%`  `            ``(g.findDisjointPaths(source, sink), source, sink)) ` ` `  ` `  `#This code is contributed by Neelam Yadav `

Output:

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

Time Complexity: Same as time complexity of Edmonds-Karp implementation of Ford-Fulkerson (See time complexity discussed here)

Graph Graph