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.

[ad type=”banner”]

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

C++ Programming:

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20find%20maximum%20number%20of%20edge%20disjoint%20paths%0A%23include%20%3Ciostream%3E%0A%23include%20%3Climits.h%3E%0A%23include%20%3Cstring.h%3E%0A%23include%20%3Cqueue%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Number%20of%20vertices%20in%20given%20graph%0A%23define%20V%208%0A%20%0A%2F*%20Returns%20true%20if%20there%20is%20a%20path%20from%20source%20’s’%20to%20sink%20’t’%20in%0A%20%20residual%20graph.%20Also%20fills%20parent%5B%5D%20to%20store%20the%20path%20*%2F%0Abool%20bfs(int%20rGraph%5BV%5D%5BV%5D%2C%20int%20s%2C%20int%20t%2C%20int%20parent%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20visited%20array%20and%20mark%20all%20vertices%20as%20not%20visited%0A%20%20%20%20bool%20visited%5BV%5D%3B%0A%20%20%20%20memset(visited%2C%200%2C%20sizeof(visited))%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20queue%2C%20enqueue%20source%20vertex%20and%20mark%20source%20vertex%0A%20%20%20%20%2F%2F%20as%20visited%0A%20%20%20%20queue%20%3Cint%3E%20q%3B%0A%20%20%20%20q.push(s)%3B%0A%20%20%20%20visited%5Bs%5D%20%3D%20true%3B%0A%20%20%20%20parent%5Bs%5D%20%3D%20-1%3B%0A%20%0A%20%20%20%20%2F%2F%20Standard%20BFS%20Loop%0A%20%20%20%20while%20(!q.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20u%20%3D%20q.front()%3B%0A%20%20%20%20%20%20%20%20q.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20for%20(int%20v%3D0%3B%20v%3CV%3B%20v%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(visited%5Bv%5D%3D%3Dfalse%20%26%26%20rGraph%5Bu%5D%5Bv%5D%20%3E%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20q.push(v)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20u%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20we%20reached%20sink%20in%20BFS%20starting%20from%20source%2C%20then%20return%0A%20%20%20%20%2F%2F%20true%2C%20else%20false%0A%20%20%20%20return%20(visited%5Bt%5D%20%3D%3D%20true)%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20tne%20maximum%20number%20of%20edge-disjoint%20paths%20from%20s%20to%20t.%0A%2F%2F%20This%20function%20is%20copy%20of%20forFulkerson()%20discussed%20at%20http%3A%2F%2Fgoo.gl%2FwtQ4Ks%0Aint%20findDisjointPaths(int%20graph%5BV%5D%5BV%5D%2C%20int%20s%2C%20int%20t)%0A%7B%0A%20%20%20%20int%20u%2C%20v%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20residual%20graph%20and%20fill%20the%20residual%20graph%20with%0A%20%20%20%20%2F%2F%20given%20capacities%20in%20the%20original%20graph%20as%20residual%20capacities%0A%20%20%20%20%2F%2F%20in%20residual%20graph%0A%20%20%20%20int%20rGraph%5BV%5D%5BV%5D%3B%20%2F%2F%20Residual%20graph%20where%20rGraph%5Bi%5D%5Bj%5D%20indicates%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20residual%20capacity%20of%20edge%20from%20i%20to%20j%20(if%20there%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20is%20an%20edge.%20If%20rGraph%5Bi%5D%5Bj%5D%20is%200%2C%20then%20there%20is%20not)%0A%20%20%20%20for%20(u%20%3D%200%3B%20u%20%3C%20V%3B%20u%2B%2B)%0A%20%20%20%20%20%20%20%20for%20(v%20%3D%200%3B%20v%20%3C%20V%3B%20v%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20rGraph%5Bu%5D%5Bv%5D%20%3D%20graph%5Bu%5D%5Bv%5D%3B%0A%20%0A%20%20%20%20int%20parent%5BV%5D%3B%20%20%2F%2F%20This%20array%20is%20filled%20by%20BFS%20and%20to%20store%20path%0A%20%0A%20%20%20%20int%20max_flow%20%3D%200%3B%20%20%2F%2F%20There%20is%20no%20flow%20initially%0A%20%0A%20%20%20%20%2F%2F%20Augment%20the%20flow%20while%20tere%20is%20path%20from%20source%20to%20sink%0A%20%20%20%20while%20(bfs(rGraph%2C%20s%2C%20t%2C%20parent))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20minimum%20residual%20capacity%20of%20the%20edges%20along%20the%0A%20%20%20%20%20%20%20%20%2F%2F%20path%20filled%20by%20BFS.%20Or%20we%20can%20say%20find%20the%20maximum%20flow%0A%20%20%20%20%20%20%20%20%2F%2F%20through%20the%20path%20found.%0A%20%20%20%20%20%20%20%20int%20path_flow%20%3D%20INT_MAX%3B%0A%20%0A%20%20%20%20%20%20%20%20for%20(v%3Dt%3B%20v!%3Ds%3B%20v%3Dparent%5Bv%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20u%20%3D%20parent%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20path_flow%20%3D%20min(path_flow%2C%20rGraph%5Bu%5D%5Bv%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20update%20residual%20capacities%20of%20the%20edges%20and%20reverse%20edges%0A%20%20%20%20%20%20%20%20%2F%2F%20along%20the%20path%0A%20%20%20%20%20%20%20%20for%20(v%3Dt%3B%20v%20!%3D%20s%3B%20v%3Dparent%5Bv%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20u%20%3D%20parent%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20rGraph%5Bu%5D%5Bv%5D%20-%3D%20path_flow%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20rGraph%5Bv%5D%5Bu%5D%20%2B%3D%20path_flow%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Add%20path%20flow%20to%20overall%20flow%0A%20%20%20%20%20%20%20%20max_flow%20%2B%3D%20path_flow%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Return%20the%20overall%20flow%20(max_flow%20is%20equal%20to%20maximum%0A%20%20%20%20%2F%2F%20number%20of%20edge-disjoint%20paths)%0A%20%20%20%20return%20max_flow%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20create%20a%20graph%20shown%20in%20the%20above%20example%0A%20%20%20%20int%20graph%5BV%5D%5BV%5D%20%3D%20%7B%20%7B0%2C%201%2C%201%2C%201%2C%200%2C%200%2C%200%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%201%2C%200%2C%200%2C%200%2C%200%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%201%2C%200%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%200%2C%200%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%201%2C%200%2C%200%2C%200%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%201%2C%200%2C%200%2C%200%2C%200%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%200%2C%200%2C%201%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%200%2C%200%2C%200%2C%200%2C%200%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20int%20s%20%3D%200%3B%0A%20%20%20%20int%20t%20%3D%207%3B%0A%20%20%20%20cout%20%3C%3C%20%22There%20can%20be%20maximum%20%22%20%3C%3C%20findDisjointPaths(graph%2C%20s%2C%20t)%0A%20%20%20%20%20%20%20%20%20%3C%3C%20%22%20edge-disjoint%20paths%20from%20%22%20%3C%3C%20s%20%3C%3C%22%20to%20%22%3C%3C%20t%20%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

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

[ad type=”banner”]