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

image processingMATLAB

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).

Best Answer

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
Related Question