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

75 views (last 30 days)

Show older comments

Mohammed Aasim Shaikh
on 27 Sep 2020

Commented: Bruno Luong
on 20 Sep 2021

##### 14 Comments

Walter Roberson
on 27 Sep 2020

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,'RecursionLimit',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
on 29 Sep 2020

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.

### Accepted Answer

Bruno Luong
on 29 Sep 2020

Edited: Bruno Luong
on 20 Nov 2020

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

##### 4 Comments

Walter Roberson
on 18 Sep 2021

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
on 20 Sep 2021

There are plenty implementations on file exchange

### More Answers (1)

Stijn Haenen
on 29 Sep 2020

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)

##### 0 Comments

### See Also

### Categories

### Community Treasure Hunt

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

Start Hunting!