What should be algorithm to find all the disjoint paths between any number of pairs of cells given in matrix?

We will say two paths will not intersect if there there is no cell common between any two paths.

My approach is : I will pick first cell pair and create a path between them. Now it will work as obstacle for path between other cell pairs. But problem is how to first pick which cell pair? Because it will create problem in finding path between some cell pair in future.

  • $\begingroup$ Your reasoning is correct. The choice of a path rules out the existence of other ones (and there is even a path which rules out the existence of any other path). I suppose what you really want to do is maximize the number of disjoint paths. If that is the case, please mention it in the answer. $\endgroup$ – dkaeae Jan 13 '19 at 9:22
  • $\begingroup$ @dkaeae I have a fixed number of cells given but pair is not fixed. It is upto us which cell we pick to make path between other given cell. $\endgroup$ – ironman Jan 13 '19 at 9:37
  • $\begingroup$ I am afraid I cannot make sense of this. What is given? What can you choose? What are you supposed to do? The question would (greatly) benefit from a formal description of the problem. $\endgroup$ – dkaeae Jan 13 '19 at 10:10
  • $\begingroup$ @dkaeae You're given a (full) grid graph and disjoint sets $S$ and $T$ of vertices with $|S|=|T|$ and you have to find a set of $|S|$ vertex-disjoint $S$-$T$ paths. (Or, possibly, you're told which $S$ vertex should be linked to which $T$ vertex; it shouldn't make much difference.) $\endgroup$ – David Richerby Jan 13 '19 at 10:20
  • $\begingroup$ @DavidRicherby Aha, so this is simply Menger's theorem restricted to matrices? $\endgroup$ – dkaeae Jan 13 '19 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.