How to find all possible pathes between source and destination?
2 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
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 commentaires
Supriya Pradhan
le 9 Mar 2017
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?
Réponses (1)
Walter Roberson
le 2 Juil 2016
https://www.mathworks.com/matlabcentral/answers/171277-how-can-i-get-all-paths-between-two-nodes#answer_165813
1 commentaire
Supriya Pradhan
le 9 Mar 2017
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?
Voir également
Catégories
En savoir plus sur Directed Graphs dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!