How to find all possible pathes between source and destination?

How to find all possible paths between points A and B. Point A[5,60] is the source, Point B[60,60] is destination.

Between points A and B, I have points C[20,80], D[40,70],E[30,30].

From the figure we can see that between points A and B there are 7 paths. So, What I need to find?:

1)Number of all possible paths and connect them in plot_figure(as shown in Figure)? Answer should be 7.

2)Number of hops and points in each path? For example in 2-path: [3 hops, 2 points]

3)The length of every hops? For example in 2-path: AC=25,CD=23, DB=22

There are some restrictions in terms of paths:

1) In each path should be no more than 3 hops.

For example the case which is shown in figure below is not acceptable.

2) Hop cannot go back to the previous point, example is shown below

So, condition for points should be like that: For example, if point E[x1,y1] and D [x2,y2]:

If x1<x2 then cancel the hop DE in path and choose another hope where x3>x2.

What I could do: I found the code to connect all points and the distance of every hope, but these code not completely appropriate for this conditions: I put all points in C matrix:

C=[5,60;60,60;20,80; 30,30;40,70];

D=5 % number of points;

[I,J] = meshgrid(1:D);

index = [I(:) J(:)].';

x11=C(:,1);

y11=C(:,2);

line(x11(index),y11(index));

d = pdist(C,'euclidean');% Find the lengh of the all hops;

Please, Can anyone help me?

[Image Analyst]

Have you looked at "Graph and Network Algorithms" in the help?

[Beibit Sautbek]

I was trying for a long time, I couldn't get the result what I need. Actually I am not professional in matlab, therefore I am asking here. Can you help me? Thank you

[David Miller]

Let X be your incidence matrix. Let X(i,j) be the element in X that corresponds to row i column j. X is a square matrix that describes what vertices are adjacent. Therefore X(i,j) = 1 if vertex i is connected to vertex j through an edge and X(i, j) = 0 if vertex i is not connected to vertex j. This will be a symmetric matrix since it is not a directed graph, therefore if vertex i is connected to vertex j then it also holds that vertex j is connected to vertex i ( X(i,j) = X(j,i) ). Also note that the diagonal will be zero since there are no loops in the graph. Now that we have this down, to figure out how many paths of length N there are between vertex i and vertex j you simply do the calculation X^N. From this resulting matrix, if you look at element X^N(i,j), it will tell you how many paths of length N there are from vertex i to vertex j. This answers (1) and (2).

*Side Note: If there is a path of length N, then there are N+1 vertices in that path***

[Rena Berman]

(Answers dev) restored question

[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?

Answer 1

[Walter Roberson]

https://www.mathworks.com/matlabcentral/answers/171277-how-can-i-get-all-paths-between-two-nodes#answer_165813

http://www.mathworks.com/matlabcentral/answers/283550-how-to-find-all-possible-paths-in-mxm-matrix

http://www.mathworks.com/matlabcentral/answers/286462-how-to-find-all-possible-paths-from-one-node-to-another-node#answer_223872

[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?