How to find all possible paths from point A to B in any direction in a matrix?

I have a MXN matrix and I select two given points A and B. How do I find and store all the possible unique paths form A to B? There are no constraint on which direction I can go from the current point, it can be up, down, left, right, or diagonal (in all four directions).

[Matt J]

It would require that M and N be very small. Even for a 10x10 matrix, it would require about 10 GB RAM.

[Mohammed Aasim Shaikh]

Okay, what if my matrix is sparse and I only want to find possible paths using just the non-zero elements? I am actually finding the possible 4, 8, or m paths in an image. The algorithm that I am thinking of applying is that I will first label the pixels (sequential labelling) according to the desired connectivity (4, 8, or m). Then if both A and B lie in the same label, I will put all other label values to zero, and find all possible paths in the remaining patch, if they have different labels then obviously there is no path possible.

[Bjorn Gustavsson]

"All the possible unique paths" I can already tell: infinity - if you dont exclude loops. have a look at graphconncomp, and the other graph functions.

[Walter Roberson]

There are an infinite number of paths. The following paths are all unique:

  A E
  A B C A E
  A B C A B C E
  A B C A B C A B C E

[Mohammed Aasim Shaikh]

I am sorry to not have mentioned it earlier, same point cannot be included twice.

[Stijn Haenen]

With this script you got all the unique paths, but it is very slow (10 minutes for a 2x3 matrix), so you have to optimize it. Optimizing shouldnt be that hard but i dont have time for it anymore.

It tries every path until it reaches to goal by going in any of the 8 directions (left right up down and diagonal).

clear
a=[1 2 3; 4 5 6];
start1=1;
start2=1;
goal1=2;
goal2=2;
abackup=a;
data=[];
for i=10^(numel(a)-1):10^numel(a)-1
    pos1=start1;
    pos2=start2;
    
    route_i=num2str(a(pos1,pos2));
    j=num2str(i);
    abackup=a;
    abackup(pos1,pos2)=NaN;
    for n=1:numel(j)
        if j(n)=='1'
            try
                if ~isnan(abackup(pos1-1,pos2))
                    pos1=pos1-1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='2'
            try
                if ~isnan(abackup(pos1-1,pos2+1))
                    pos1=pos1-1;
                    pos2=pos2+1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='3'
            try
                if ~isnan(abackup(pos1,pos2+1))
                    pos2=pos2+1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='4'
            try
                if ~isnan(abackup(pos1+1,pos2+1))
                    pos1=pos1+1;
                    pos2=pos2+1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='5'
            try
                if ~isnan(abackup(pos1+1,pos2))
                    pos1=pos1+1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='6'
            try
                if ~isnan(abackup(pos1+1,pos2-1))
                    pos1=pos1+1;
                    pos2=pos2-1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='7'
            try
                if ~isnan(abackup(pos1,pos2-1))
                    pos2=pos2-1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='8'
            try
                if ~isnan(abackup(pos1-1,pos2-1))
                    pos1=pos1-1;
                    pos2=pos2-1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        
    end
end
unique(data)

[Mohammed Aasim Shaikh]

Thank you very much, I will try this one.

[Bruno Luong]

If you want to label the region there is better reason not to search for all the paths between two arbitrary points. This brute force a waste of time and very inefficient (even infeasible for medium connectivity).

[Mohammed Aasim Shaikh]

@Bruno Yes, I understand. If there was a way to define a recursive function in MATLAB, it would have been a lot easier.

[Mohammed Aasim Shaikh]

Yes sure. That would be very helpful.

[Walter Roberson]

What is "m path" ?

[Walter Roberson]

I would recommend a breadth-first search.

https://www.mathworks.com/matlabcentral/answers/470708-matlab-built-in-function-to-retrieve-all-possible-paths-between-two-nodes#comment_722515 except that you would not stop looking as soon as you found the first path.

[Walter Roberson]

MATLAB permits recursive functions, using the same syntax as most other programming languages -- which is to say that you just place a call to the function you are in the middle of defining.

The limitation on recursion in MATLAB is that by default only 500 levels of recursion are permitted. However, you can change that by using

set(0,'Rec​ursionLimi​t',N)

where N is your new depth limit. Be warned that if you do this, then there is a risk of crashing the computation by running out of stack space, as each call takes up memory (a copy of all local variables must be saved.)

[John D'Errico]

The important point to reconize is just the sheer enormity of the number of all possilbe paths, even for a small matrix.

Almost always there are better ways to solve a problem than a complete sampling of the space you wish to investigate. This is why optimization methods exist, to help you to avoid brute force sampling schemes.

Answer 1

[Bruno Luong]

Tiny matrix of size 4 x 3.

All paths of two opposite corners:

• 38 paths for 4-connectivity,
• 2922 paths for 8-connectivity

clear
close all

m=4; n=3;
% Adjacent matrix of a graph of 4-connected grid of size m x n
[X,Y] = meshgrid(1:n,1:m);
mxn = numel(X);
I = sub2ind(size(X),Y(1:end-1,:),X(1:end-1,:));
J = I+1;
A = sparse(I,J,1,mxn,mxn);
I = sub2ind(size(X),Y(:,1:end-1),X(:,1:end-1));
J = I+size(X,1);
A = A + sparse(I,J,1,mxn,mxn);
A4 = A + A';
% Adjacent matrix of a graph of 8-connected grid of size m x n
I = sub2ind(size(X),Y(1:end-1,1:end-1),X(1:end-1,1:end-1));
J = I+size(X,1)+1;
A = A + sparse(I,J,1,mxn,mxn);
I = sub2ind(size(X),Y(2:end,1:end-1),X(2:end,1:end-1));
J = I+size(X,1)-1;
A = A + sparse(I,J,1,mxn,mxn);
A8 = A + A';

% source and destination
is = 1; js = 1;
id = m; jd = n;
s = sub2ind([m,n],is,js);
d = sub2ind([m,n],id,jd);

allp4 = AllPath(A4, s, d);
PlotandAnimation(4, A4, allp4, [m,n]);

allp8 = AllPath(A8, s, d);
PlotandAnimation(8, A8, allp8, [m,n]);

%%
function PlotandAnimation(nc, A, allp, sz)
fprintf('%d-connected %d x %d\n', nc, sz);
% Plot and animation
figure
[i,j] = ind2sub(sz,1:prod(sz));
nodenames = arrayfun(@(i,j) sprintf('(%d,%d)', i, j), i, j, 'unif', 0);
G = graph(A);
h = plot(G);
labelnode(h, 1:prod(sz), nodenames)
th = title('');
colormap([0.6; 0]*[1 1 1]);
E = table2array(G.Edges);
E = sort(E(:,1:2),2);
np = length(allp);
for k=1:np
    pk = allp{k};
    pkstr = nodenames(pk);
    s = sprintf('%s -> ',pkstr{:});
    s(end-3:end) = [];
    fprintf('%s\n', s);
    Ek = sort([pk(1:end-1); pk(2:end)],1)';
    b = ismember(E, Ek, 'rows');
    set(h, 'EdgeCData', b, 'LineWidth', 0.5+1.5*b);
    set(th, 'String', sprintf('%d-connected, path %d/%d', nc, k, np));
    pause(0.1);
end
end

%%
% EDIT: better code available in the comment
function p = AllPath(A, s, t)
% Find all paths from node #s to node #t
% INPUTS:
%   A is (n x n) symmetric ajadcent matrix
%   s, t are node number, in (1:n)
% OUTPUT
%   p is M x 1 cell array, each contains array of
%   nodes of the path, (it starts with s ends with t)
%   nodes are visited at most once.

if s == t
    p =  {s};
    return
end
p = {};
As = A(:,s)';
As(s) = 0;
neig = find(As);
if isempty(neig)
    return
end
A(:,s) = [];
A(s,:) = [];
neig = neig-(neig>=s);
t = t-(t>=s); 
for n=neig
    p = [p; AllPath(A,n,t)]; %#ok
end
p = cellfun(@(a) [s, a+(a>=s)], p, 'unif', 0);
end %AllPath

[Bruno Luong]

I update here the function Allpath to work on directgraph as well. For dirgraph, if t parameter is NaN this function returns all the path started from s and ended to leaf.

NOTE: It continues to work on undirect graph.

function p = AllPath(A, s, t)
% Find all paths from node #s to node #t
% INPUTS:
%   A is (n x n) ajadcent matrix (preferable sparse)
%       it can be symmetric (graph) or unsymmetric (digraph)
%   s, t are node number, in (1:n)
%   NOTE: for digraph, if t is NaN, all paths started from s and ended at a
%       leaf are returned
% OUTPUT
%   p is M x 1 cell array, each contains array of
%   nodes of the path, (it starts with s ends with t)
%   Nodes are visited at most once.
%
% Author: <Bruno Luong> [e-mail]
%
if isgraph(A)
    % graph
    G = graph(A);
    [~, d] = shortestpath(G, s, t);
    if isfinite(d)
        p = AllPathHelper(A, s, t);
    else
        p = {};
    end
else
    % digraph
    if nargin < 3 || isempty(t)
        t = NaN;
    end
    tnotprovide = ~isfinite(t);
    if tnotprovide
        % connect the leaf to a single dummy node t
        n = size(A,2);
        [ss,tt] = find(A);
        leaf = setdiff(tt,ss);
        A(n+1,n+1) = 0;
        A(:,n+1) = sparse(leaf, 1, 1, n+1, 1);
        t = n+1;
    end
    G = digraph(A);
    [~, d] = shortestpath(G, s, t);
    if isfinite(d)
        p = AllPathHelper(A.', s, t);
        if tnotprovide
            % remove the dummy node
            for k=1:length(p)
                p{k} = p{k}(1:end-1);
            end
        end
    else
        p = {};
    end
end
end % AllPath

%%
function tf = isgraph(A)
A = spones(A);
tf = nnz(A-A')==0;
end % isgraph

%%
function p = AllPathHelper(AT, s, t)
% Find all paths from node #s to node #t
% INPUTS:
%   AT is (n x n) transposed of the ajadcent matrix
%   s, t are node number, in (1:n)
% OUTPUT
%   p is M x 1 cell array, each contains array of
%   nodes of the path, (it starts with s ends with t)
%   nodes are visited at most once.

if s == t
    p =  {s};
    return
end
p = {};
As = AT(:,s);
As(s) = 0;
if nnz(As)==0
    return
end
neig = find(As);
AT(:,s) = 0;
AT(s,:) = 0;
neig = reshape(neig,1,[]);
for n=neig
    p = [p; AllPathHelper(AT,n,t)]; %#ok
end
for k=1:length(p)
    p{k} = [s, p{k}];
end
end % AllPathHelper

[Jagan Mohan Reddy Danda]

How to find shortest path of a given graph without using in-built function?

[Walter Roberson]

Jagan, read about:

• breadth-first search (bfs() in MATLAB)
• A* algorithm (less common)
• Dijkstra's algorithm (very common approach)

If what you need is the "cost" of the shortest path and not the particular edges, then there is an algorithm involving matrix multiplication.

[Bruno Luong]

There are plenty implementations on file exchange

https://www.mathworks.com/matlabcentral/fileexchange?q=shortest+path

Answer 2

[Stijn Haenen]

With this script you got all possible paths, but it is very slow so you have to optimize it (shouldnt be that hard but dont have time for it anymore).

The script tries every path by going in any of the 8 directions at every step until it reaches its goal position.

clear
a=[1 2 3; 4 5 6];
start1=1;
start2=1;
goal1=2;
goal2=2;
abackup=a;
data=[];
for i=10^(numel(a)-1):10^numel(a)-1
    pos1=start1;
    pos2=start2;
    
    route_i=num2str(a(pos1,pos2));
    j=num2str(i);
    abackup=a;
    abackup(pos1,pos2)=NaN;
    for n=1:numel(j)
        if j(n)=='1'
            try
                if ~isnan(abackup(pos1-1,pos2))
                    pos1=pos1-1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='2'
            try
                if ~isnan(abackup(pos1-1,pos2+1))
                    pos1=pos1-1;
                    pos2=pos2+1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='3'
            try
                if ~isnan(abackup(pos1,pos2+1))
                    pos2=pos2+1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='4'
            try
                if ~isnan(abackup(pos1+1,pos2+1))
                    pos1=pos1+1;
                    pos2=pos2+1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='5'
            try
                if ~isnan(abackup(pos1+1,pos2))
                    pos1=pos1+1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='6'
            try
                if ~isnan(abackup(pos1+1,pos2-1))
                    pos1=pos1+1;
                    pos2=pos2-1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='7'
            try
                if ~isnan(abackup(pos1,pos2-1))
                    pos2=pos2-1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        if j(n)=='8'
            try
                if ~isnan(abackup(pos1-1,pos2-1))
                    pos1=pos1-1;
                    pos2=pos2-1;
                    route_i=sprintf('%s%g',route_i,a(pos1,pos2));
                    abackup(pos1,pos2)=NaN;
                    if pos1==goal1 && pos2==goal2
                        data(end+1)=str2num(route_i);break
                    end
                end
            catch
            end
        end
        
    end
end
unique(data)