How to find all possible routes with a given node matrix?
2 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Jung Sunghun
el 25 de Abr. de 2018
Comentada: Jung Sunghun
el 20 de Oct. de 2018
Hello,
I am trying to write a function to find all possible routes from the Start node, 6, to the Goal node, 21, with the given node matrix, A, as shown in the below.
A =
1 6
1 23
2 3
2 4
2 5
3 2
4 2
4 7
5 2
5 11
6 1
6 26
7 4
7 8
8 7
8 9
8 24
9 8
9 23
10 11
10 13
10 15
10 16
11 5
11 10
12 13
12 14
13 10
13 12
13 24
14 12
14 19
15 10
15 17
16 10
16 17
16 18
17 15
17 16
17 25
18 16
18 19
18 22
19 14
19 18
19 20
20 19
21 22
21 27
22 18
22 21
22 25
23 1
23 9
24 8
24 13
25 17
25 22
26 6
27 21
I would like to build a function which results the following outputs.
[6,1,23,9,8,7,4,2,5,11,10,15,17,25,22,21]
[6,1,23,9,8,7,4,2,5,11,10,15,17,16,18,22,21]
[6,1,23,9,8,7,4,2,5,11,10,16,17,25,22,21]
[6,1,23,9,8,7,4,2,5,11,10,16,18,22,21]
[6,1,23,9,8,24,13,10,15,17,25,22,21]
[6,1,23,9,8,24,13,10,16,17,25,22,21]
[6,1,23,9,8,24,13,10,16,18,22,21]
[6,1,23,9,8,24,13,12,14,19,18,16,10,15,17,25,22,21]
[6,1,23,9,8,24,13,12,14,19,18,16,17,25,22,21]
[6,1,23,9,8,24,13,12,14,19,18,22,21]
Thank you very much for your invaluable time to help on this problem.
Best regards,
Sunghun Jung
3 comentarios
Walter Roberson
el 15 de Oct. de 2018
You effectively have an undirected graph. There are an infinite number of routes unless you add constraints.
Respuesta aceptada
Bruno Luong
el 15 de Oct. de 2018
Editada: Bruno Luong
el 15 de Oct. de 2018
I found actually 13 paths, more than the 10 you have listed:
[6 1 23 9 8 7 4 2 5 11 10 13 12 14 19 18 16 17 25 22 21]
[6 1 23 9 8 7 4 2 5 11 10 13 12 14 19 18 22 21]
[6 1 23 9 8 7 4 2 5 11 10 15 17 16 18 22 21]
[6 1 23 9 8 7 4 2 5 11 10 15 17 25 22 21]
[6 1 23 9 8 7 4 2 5 11 10 16 17 25 22 21]
[6 1 23 9 8 7 4 2 5 11 10 16 18 22 21]
[6 1 23 9 8 24 13 10 15 17 16 18 22 21]
[6 1 23 9 8 24 13 10 15 17 25 22 21]
[6 1 23 9 8 24 13 10 16 17 25 22 21]
[6 1 23 9 8 24 13 10 16 18 22 21]
[6 1 23 9 8 24 13 12 14 19 18 16 10 15 17 25 22 21]
[6 1 23 9 8 24 13 12 14 19 18 16 17 25 22 21]
[6 1 23 9 8 24 13 12 14 19 18 22 21]
Test code:
A =[ 1 6
1 23
2 3
2 4
2 5
3 2
4 2
4 7
5 2
5 11
6 1
6 26
7 4
7 8
8 7
8 9
8 24
9 8
9 23
10 11
10 13
10 15
10 16
11 5
11 10
12 13
12 14
13 10
13 12
13 24
14 12
14 19
15 10
15 17
16 10
16 17
16 18
17 15
17 16
17 25
18 16
18 19
18 22
19 14
19 18
19 20
20 19
21 22
21 27
22 18
22 21
22 25
23 1
23 9
24 8
24 13
25 17
25 22
26 6
27 21];
p = gallpaths(A,6,21);
for k=1:length(p)
fprintf('%s\n', mat2str(p{k}));
end
Using this function GALLPATHS I made
function p = gallpaths(A,start,last)
% find all direct paths from start to last
% A is (n x 2) each row is an edges
A = sortrows(A);
b = true(size(A,1),1);
p = gapengine(A,b,start,last);
end
function p = gapengine(A,b,start,last)
% recursive engine
if start==last
p = {last};
else
bs = A(:,1) == start;
next = A(bs & b,2);
p = {};
b(bs) = false;
for k=1:length(next)
i = next(k);
pk = gapengine(A,b,i,last);
pk = cellfun(@(p) [start, p], pk, 'unif', 0);
p = [p, pk];
end
end
end
3 comentarios
Bruno Luong
el 15 de Oct. de 2018
Nope find all paths has exponential complexity. AFAIK this is intrinsic to the problem you want to solve rather than the algorithm.
Más respuestas (1)
Walter Roberson
el 15 de Oct. de 2018
2 comentarios
Walter Roberson
el 19 de Oct. de 2018
See also https://www.geeksforgeeks.org/find-paths-given-source-destination/ which gives code in C, Java, and Python.
Ver también
Categorías
Más información sobre Variables 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!