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].
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
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!