CODEWITHSUNDEEP
algorithmdirected-graphmax-flow
Ankit Mishra
Ankit Mishra

Reputation: 409

K edge disjoint paths in a directed graph

Give two vertices u and v in G = (V,E) and a positive integer k, describe an algorithm to decide if there exists a k edge disjoint paths from u to v. If the answer to the decision problem is yes, describe how to compute a set of k edge disjoint paths.

Solution : Run max flow from u to v (giving all edges in the Graph G a weight of 1 so that one edge can be part of only one path from u to v) and get the value of flow. If the value of the flow is k then we have the answer to the decision problem as yes.

Now for finding all such paths find the min cut by doing BFS from u and hence I will have the partition of vertices which will separate the vertices into 2 sets one on each side of min cut.

Then do I need to again do a DFS from u to v looking for all the paths which have only these vertices which are there in the two partition set that I got from the min cut.

Or is there any other cleaner way ? to get all the k edge disjoint paths.

Upvotes: 3

Views: 2532

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Once you have the flow you can extract the edge disjoint paths by following the flow.

The start node will have a flow of k leaving u along k edges.

For each of these edges you can keep moving in the direction of outgoing flow to extract the path until you reach v. All you need to do is to mark the edges you have already used to avoid duplicating edges.

Repeat for each of the k units of flow leaving u to extract all k paths.

Pseudocode

repeat k times:
  set x to start node
  set path to []
  while x is not equal to end node:
      find a edge from x which has flow>0, let y be the vertex at the far end
      decrease flow from x->y by 1 unit
      append y to path
      set x equal to y
  print path

Upvotes: 4

Related Questions