How to find all possible pathes between source and destination?

Question

Beibit Sautbek 2016-7-2

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/293441-how-to-find-all-possible-pathes-between-source-and-destination

评论： Supriya Pradhan 2017-3-9

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?

5 个评论
显示 3更早的评论隐藏 3更早的评论

David Miller 2016-7-2

编辑：Walter Roberson 2016-8-27

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 2016-10-30

(Answers dev) restored question

Supriya Pradhan 2017-3-9

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 2016-7-2

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/293441-how-to-find-all-possible-pathes-between-source-and-destination#answer_227443

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

1 个评论
显示 -1更早的评论隐藏 -1更早的评论