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

clearclose allm=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 nI = 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 destinationis = 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 animationfigure[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);endend%%% EDIT: better code available in the commentfunction 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};    returnendp = {};As = A(:,s)';As(s) = 0;neig = find(As);if isempty(neig)    returnendA(:,s) = [];A(s,:) = [];neig = neig-(neig>=s);t = t-(t>=s); for n=neig    p = [p; AllPath(A,n,t)]; %#okendp = cellfun(@(a) [s, a+(a>=s)], p, 'unif', 0);end %AllPath