How to find all possible routes with a given node matrix?

25 Avr 2018
2 Réponses
Réponse acceptée
Mise à jour 20 Oct 2018
13 Vues (30 jours)

0 votes

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 commentaires
Afficher 1 commentaire plus ancien Masquer 1 commentaire plus ancien

Jung Sunghun
Jung Sunghun le 15 Oct 2018
Is there anyone who can help this question?
Walter Roberson
Walter Roberson le 15 Oct 2018
You effectively have an undirected graph. There are an infinite number of routes unless you add constraints.
Jung Sunghun
Jung Sunghun le 15 Oct 2018
Dear Sir,
The constraint is that the node could only be used once in the path.

Connectez-vous pour commenter.

Connectez-vous pour répondre à cette question.

 Réponse acceptée

Bruno Luong
Bruno Luong le 15 Oct 2018
Modifié(e) : Bruno Luong le 15 Oct 2018

2 votes

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 commentaires
Afficher 1 commentaire plus ancien Masquer 1 commentaire plus ancien

Jung Sunghun
Jung Sunghun le 15 Oct 2018
Modifié(e) : Jung Sunghun le 15 Oct 2018
Dear sir,
The code works great. Thank you very much.
However, when I increased the number of node in A matrix as shown in the below, it runs forever...
Is there any method to minimize computation time?
---
A =
1 2
1 14
1 15
1 180
2 1
2 14
2 15
2 20
3 8
3 9
3 10
4 6
4 11
4 12
5 11
5 17
6 4
6 9
6 13
7 9
7 21
7 22
7 28
8 3
8 27
9 3
9 6
9 7
10 3
10 21
10 27
10 28
11 4
11 5
12 4
12 36
12 181
13 6
13 22
13 25
14 1
14 2
14 16
14 19
15 1
15 2
15 210
16 14
16 18
16 180
17 5
17 18
17 26
18 16
18 17
19 14
19 31
20 2
20 23
20 32
21 7
21 10
21 33
22 7
22 13
22 29
23 20
23 31
23 32
24 27
24 34
24 41
24 65
25 13
25 35
25 36
26 17
26 30
26 181
27 8
27 10
27 24
28 7
28 10
28 34
29 22
29 33
29 35
30 26
30 37
31 19
31 23
31 182
31 186
32 20
32 23
32 43
33 21
33 29
33 38
34 24
34 28
34 41
34 42
35 25
35 29
35 39
36 12
36 25
36 37
37 30
37 36
37 40
38 33
38 52
38 183
39 35
39 44
39 45
40 37
40 55
40 187
41 24
41 34
41 50
42 34
42 52
42 54
43 32
43 46
43 47
44 39
44 48
44 183
45 39
45 55
45 62
46 43
46 182
46 184
47 43
47 57
48 44
48 56
48 61
49 51
49 59
49 60
50 41
50 54
50 65
51 49
51 58
51 185
51 188
52 38
52 42
52 56
53 55
53 58
53 66
54 42
54 50
54 64
55 40
55 45
55 53
56 48
56 52
56 63
57 47
57 60
57 67
58 51
58 53
59 49
59 184
59 186
60 49
60 57
60 68
61 48
61 62
61 72
61 77
62 45
62 61
62 69
63 56
63 72
63 77
63 189
64 54
64 74
64 75
65 24
65 50
65 81
66 53
66 70
66 71
67 57
67 76
68 60
68 73
68 78
68 79
69 62
69 72
69 84
70 66
70 82
70 84
71 66
71 73
71 79
71 188
72 61
72 63
72 69
73 68
73 71
73 82
74 64
74 80
74 189
75 64
75 81
75 96
76 67
76 78
76 190
77 61
77 63
77 85
78 68
78 76
78 86
79 68
79 71
79 83
80 74
80 89
80 192
81 65
81 75
81 90
82 70
82 73
82 91
83 79
83 87
83 88
84 69
84 70
84 191
85 77
85 89
85 92
86 78
86 87
86 95
87 83
87 86
87 97
88 83
88 91
88 98
89 80
89 85
89 93
90 81
90 109
90 110
91 82
91 88
91 94
92 85
92 100
92 191
93 89
93 105
93 111
94 91
94 100
94 102
95 86
95 99
95 190
96 75
96 106
96 107
97 87
97 101
97 104
98 88
98 101
98 102
99 95
99 104
99 193
100 92
100 94
100 103
101 97
101 98
101 115
102 94
102 98
102 108
103 100
103 111
103 112
104 97
104 99
104 113
105 93
105 106
105 116
106 96
106 105
106 192
107 96
107 109
107 194
108 102
108 117
108 119
109 90
109 107
109 114
110 90
110 134
110 198
111 93
111 103
111 195
112 103
112 117
112 118
113 104
113 120
113 121
114 109
114 130
114 198
115 101
115 119
115 120
116 105
116 122
116 196
117 108
117 112
117 126
118 112
118 125
118 197
119 108
119 115
119 123
120 113
120 115
120 124
121 113
121 127
121 193
122 116
122 128
122 129
123 119
123 124
123 136
124 120
124 123
124 135
125 118
125 195
125 196
126 117
126 136
126 137
127 121
127 135
127 150
128 122
128 133
129 122
129 145
129 146
130 114
130 131
130 132
131 130
131 133
131 194
132 130
132 142
132 200
133 128
133 131
133 138
134 110
134 143
134 200
135 124
135 127
135 148
136 123
136 126
136 139
137 126
137 140
137 199
138 133
138 142
138 147
139 136
139 151
139 152
140 137
140 141
140 197
141 140
141 144
141 201
142 132
142 138
142 149
143 134
143 153
143 159
144 141
144 151
144 199
145 129
145 201
145 202
146 129
146 147
146 158
147 138
147 146
147 149
148 135
148 157
149 142
149 147
149 153
150 127
150 161
150 166
151 139
151 144
151 154
152 139
152 155
152 157
153 143
153 149
153 156
153 176
154 151
154 155
154 203
155 152
155 154
155 160
156 153
156 172
157 148
157 152
157 161
158 146
158 163
158 164
159 143
159 173
159 206
160 155
160 162
160 205
161 150
161 157
161 165
162 160
162 167
162 203
163 158
163 202
163 204
164 158
164 168
164 169
165 161
165 178
165 208
166 150
166 179
166 208
167 162
167 170
167 171
168 164
168 170
168 175
169 164
169 172
169 175
170 167
170 168
170 204
171 167
171 175
171 178
172 156
172 169
172 209
173 159
173 207
173 211
174 176
174 177
174 206
175 168
175 169
175 171
176 153
176 174
177 174
177 207
177 209
178 165
178 171
178 205
179 166
180 1
180 16
181 12
181 26
182 31
182 46
183 38
183 44
184 46
184 59
184 185
185 51
185 184
185 187
186 31
186 59
187 40
187 185
188 51
188 71
189 63
189 74
190 76
190 95
191 84
191 92
192 80
192 106
193 99
193 121
194 107
194 131
195 111
195 125
196 116
196 125
197 118
197 140
198 110
198 114
199 137
199 144
200 132
200 134
201 141
201 145
202 145
202 163
203 154
203 162
204 163
204 170
205 160
205 178
206 159
206 174
207 173
207 177
208 165
208 166
209 172
209 177
210 15
211 173
Bruno Luong
Bruno Luong le 15 Oct 2018
Nope find all paths has exponential complexity. AFAIK this is intrinsic to the problem you want to solve rather than the algorithm.
Jung Sunghun
Jung Sunghun le 15 Oct 2018
I got it. Thank you very much for your invaluable time. Have a great day!

Connectez-vous pour commenter.

Catégories

En savoir plus sur Function Creation dans Centre d'aide et File Exchange

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by