How to find all possible pathes between source and destination?
2 次查看(过去 30 天)
显示 更早的评论
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].
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/154633/image.png)
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.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/154634/image.png)
2) Hop cannot go back to the previous point, example is shown below
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/154635/image.png)
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 个评论
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?
回答(1 个)
Walter Roberson
2016-7-2
https://www.mathworks.com/matlabcentral/answers/171277-how-can-i-get-all-paths-between-two-nodes#answer_165813
1 个评论
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?
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Directed Graphs 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!