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

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

[Jung Sunghun]

Is there anyone who can help this question?

[Walter Roberson]

You effectively have an undirected graph. There are an infinite number of routes unless you add constraints.

[Jung Sunghun]

Dear Sir,

The constraint is that the node could only be used once in the path.

Answer 1

[Bruno Luong]

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

[Jung Sunghun]

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]

Nope find all paths has exponential complexity. AFAIK this is intrinsic to the problem you want to solve rather than the algorithm.

[Jung Sunghun]

I got it. Thank you very much for your invaluable time. Have a great day!

Answer 2

[Walter Roberson]

See https://www.mathworks.com/matlabcentral/answers/286462-how-to-find-all-possible-paths-from-one-node-to-another-node#answer_223872

[Walter Roberson]

See also https://www.geeksforgeeks.org/find-paths-given-source-destination/ which gives code in C, Java, and Python.

[Jung Sunghun]

Thank you very much for the kind supporting.