how to find all possible paths in MxM matrix

how to find all possible paths in MxN matrix with constraint at any cell path will move to next cell which at right directly or diagonally right up or down Note that number of paths will equal M^N for example if we have 2x3 matrix [1 3 5 ; 2 4 6 ] paths will be 1- 1,3,5--> 2- 1,3,6--> 3- 1,4,5--> 4- 1,4,6--> 5- 2,3,5--> 6- 2,3,6--> 7- 2,4,5--> 8- 2,4,6--> please any one know how to solve this problem contact with me ASAP

[Guillaume]

"Note that number of paths will equal M^N"

No it won't. From each node, you have at most 3 paths to choose from, so an upper bound is M * 3^N. In practice, it'll be much lower since you'll hit the top and bottom edges often, so a lot of time you're limited to 2 paths to choose from. A lower bound is M * 2^N.

[Supriya Pradhan]

find all possible path between 2 nodes in an un-directed graph with preventing duplicate nodes.

Hi, I'm very new to MATLAB and am having some trouble. this is my graph below :

s = [1 1 1 1 5 5 4 4 3 3 2 6 6 7 7 8 8 9 13 13 12 12 11 11 11 10 14 14 15 15 15 16 16 17 21 21 20 20 19 19 19 18 22 23 24];

d = [5 4 3 2 6 7 7 3 8 2 9 13 7 8 12 9 11 10 14 12 15 11 16 10 17 17 21 15 20 16 19 19 17 18 22 20 23 22 23 24 18 25 25 25 25];

names = {'A' 'E' 'D' 'C' 'B' 'I' 'H' 'G' 'F' 'M' 'L' 'K' 'J' 'Q' 'P' 'O' 'N' 'U' 'T' 'S' 'R' 'X' 'W' 'V' 'Y'};

w = [8 5 2 6 6 5 3 2 5 2 5 5 3 3 4 3 6 6 8 5 7 4 8 3 7 8 10 4 7 9 6 5 9 6 4 1 9 5 9 9 1 13 12 8 7];

G = graph(s,d,w,names);

G.Edges

plot(G);

i want 2 find all possible path from this graph. like if user will give input as source = 1 and destination = 25 then in between 1-25 all possible path have to show with preventing duplicate nodes. Please, Can anyone help me?

[Guillaume]

@Supriya,

start your own question

Answer 1

[John D'Errico]

No. I'm not going to write the code for you, as this is probably either homework or possibly something like a project Euler problem. In any case, you will learn by making an effort, so writing code for it for you would be inappropriate. To be honest, even what I'll say may be more of a hint than is appropriate, since it really gives the whole thing away.

A simple loop seems logical. Start at the top left. Keep a record of all paths that end at each point. Then consider that it is irrelevant how you got to a certain point, only that you got there, and the possible places you can go onwards.

So, to start with, the first path is just point 1. From there, you can move down, right, or diagonally down, resulting in the paths {[1 3],[1 2],[1 4]}.

There are now only 3 points to worry about, the paths that start from 2, 3, or 4.

Lather, rinse, and repeat, creating a tree of all possible paths.

[Mohammad Alsalamin]

i wrote code for this problem but it require alot of time when number of columns since each column require for loop thus nested for will take alot of time

Answer 2

[Guillaume]

I would actually start from right to left. For each row build the list of the two or three rows you can reach. Add the list of rows these could reach on the previous to these and repeat until the first column.

This build the list of rows indices of the tree:

function p = pathbuilder(nrows, ncols)
   %p: a matrix where each row is a path. Each element is the row to pick for the corresponding column
   %nrows: the number of starting nodes in the tree
   %ncols: the number of levels in the tree
   p = num2cell((1:nrows)');
   for c = 1:ncols-1;
      p = arrayfun(@(r) cell2mat(arrayfun(@(rr) [repmat(r, size(p{rr}, 1), 1), p{rr}], ...
                                       (max(1, r-1):min(nrows, r+1))', ...
                                       'UniformOutput', false)), ...
                   (1:nrows)', ...
                   'UniformOutput', false);
   end
   p = cell2mat(p);
end

[Mohammad Alsalamin]

please look on the picture attached with this comment i want the paths with that constraint thanks alot

[Guillaume]

There is no constraint in your picture. It's simply the cartesian product of the columns. This is trivial to obtain and there are files on the FileExchange that do this for you.

As John said, "you will learn by making an effort". The code I wrote calculates the paths according to your initial requirement, It is trivial to transform its output into what you were originally asking.

[Mohammad Alsalamin]

could you please open the attachment to know what i was exactly mean by saying constraint. look how the paths are generated thanks alot for your time

[Guillaume]

Sorry, I'm not opening an excel file with macros coming from an unknown source. Copy your data and paste it as text into a comment.

[Mohammad Alsalamin]

<<

>>

[Mohammad Alsalamin]

these are not all possible paths in the matrix but i want paths as they appear on the attchaed pictures thanks

[Guillaume]

As far as I can tell, you've reposted exactly the same thing as your image, just in a different format.

As I said you're now asking for the cartesian product of the columns, which has nothing to do with your original question.

As also said there are submissions for this on the File exchange. It's also trivial to obtain

M = reshape(1:24, 4, 6);
columns = num2cell(M, 1);
combs = cell(size(columns));
[combs{:}] = ndgrid(columns{:});
combs = cellfun(@(c) c(:), combs, 'UniformOutput', false);
combs = [combs{:}]

[kd p]

How do you define the input variables

Answer 3

[Roger Stafford]

@Mohammad: Here is code that does not require any rejections - every row of matrix A represents a valid “path”. It differs from your request in that the result in A contains row indices instead of the contents of your data matrix, with the column indices being understood from their position in the columns of A. For example, if M = 7 and N = 6, one of the rows of A would be: 7 7 6 5 4 5. These represent the indices (7,1), (7,2), (6,3), (5,4), (4,5), and (5,6) in an M-by-N data matrix. To achieve just what you requested either use values in A as indices into your data matrix, or there are three places in the code below that can be altered so as to accomplish this, which I indicate with asterisks.

   T = zeros(M+2,N);
   T(2:M+1,N) = ones(M,1);
   for k = N-1:-1:1
     T(2:M+1,k) = T(1:M,k+1)+T(2:M+1,k+1)+T(3:M+2,k+1);
   end
   T = cumsum(T);
   A = zeros(T(M+2,1),N); % Allocate the necessary size for A
   A(1:M,N) = (1:M).';  % <-- ******
   for j = N-1:-1:1
     for k = M+1:-1:3
       A(T(k-1,j)+1:T(k,j),j+1:N) = A(T(k-2,j+1)+1:T(k+1,j+1),j+1:N);
       A(T(k-1,j)+1:T(k,j),j) = k-1;  % <-- ******
     end
     A(T(1,j)+1:T(2,j),j) = 1;  % <-- ******
   end

[Guillaume]

Hum, that's interesting. I thought that my pathbuilder code that uses cell arrays and anonymous function to build the paths would be significantly slower than a pure matrix approach, but it's at least twice as fast on my computer.