How to find all possible pathes between source and destination?
4 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Supriya Pradhan
el 9 de Mzo. de 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?
Respuestas (1)
Walter Roberson
el 2 de Jul. de 2016
https://www.mathworks.com/matlabcentral/answers/171277-how-can-i-get-all-paths-between-two-nodes#answer_165813
1 comentario
Supriya Pradhan
el 9 de Mzo. de 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?
Ver también
Categorías
Más información sobre Graph and Network Algorithms en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!