Shortest Path in a 3D Matrix

15 views (last 30 days)
I have a 3D matrix with all 1 or 0 and two random elements. How can I calculate the shortest path between them and check how many elements with 1 are in the path? Thanks in advance.
Image Analyst
Image Analyst on 2 Jun 2015
Steve talks about the non-uniqueness of paths in part 2 of his blog:

Sign in to comment.

Accepted Answer

Alfonso Nieto-Castanon
Alfonso Nieto-Castanon on 3 Jun 2015
If you do not really care too much about the 'uniqueness' issue brought up in the comments, and just want to consider a single "straight" trajectory, you could do something like:
BW = rand([50 50 50])>.25; % your 3d matrix
i1 = [3, 2, 20]; % coordinates of initial point
i2 = [6, 10, 25]; % coordinates of end point
n = max(abs(i2-i1))+1; % number of steps
i = arrayfun(@(a,b)round(linspace(a,b,n)),i1,i2,'uni',0);
idx = sub2ind(size(BW),i{:});
sumBW = nnz(BW(idx));
disp(cell2mat(i')); % display trajectory
disp(sumBW); % display number of 1's in path
In this example, the trajectory chosen between [3,2,20] and [6,10,25] would be:
3 3 4 4 5 5 5 6 6
2 3 4 5 6 7 8 9 10
20 21 21 22 23 23 24 24 25
Marta Alcalde
Marta Alcalde on 28 Jun 2022
Yes, it would be useful for me if you explain a little bit the general idea behind your code. I would like to obtain the trajectory (cell2mat(i') in the previous code) but I have no clue how to obtain it.

Sign in to comment.

More Answers (3)

Walter Roberson
Walter Roberson on 2 Jun 2015
The same way as with a 2D matrix; you build a connectivity list and run a shortest path algorithm on it.

Image Analyst
Image Analyst on 2 Jun 2015
Steve has a blog on that: though I don't know if bwdistgeodesic works on 3D images.
Image Analyst
Image Analyst on 3 Jun 2015
Alex, I don't think the documentation is entirely clear. All the help says is "BW is a logical matrix." I've seen some people say "matrix" means only a 2-D array whereas anything 3-D or higher should be called "array" instead of "matrix." I'm not sure I agree with that, and sometimes I use them interchangeably. But nonetheless I think the documentation could be clearer on the dimensionality that it accepts. If it works for a n-D array where n can be any integer, then it might say that explicitly. Sometime you have separate n versions of functions, like convhull and convhulln, and bwlabel and bwlabeln. So sometimes people assume it's only 2-D unless it makes it clear in the documentation that it's for n-D.

Sign in to comment.

ahmad karim
ahmad karim on 3 Jun 2015
Plese, i have travelling salesman cost function but its give me error when i implement it plese can any one help me ?
% cost function for traveling salesperson problem % Haupt & Haupt % 2003 function dist=tspfun(pop) global iga x y [Npop,Ncity]=size(pop); tour=[pop pop(:,1)]; %distance between cities for ic=1:Ncity for id=1:Ncity dcity(ic,id)=sqrt((x(ic)-x(id))^2+(y(ic)-y(id))^2); end % id end %ic % cost of each chromosome for ic=1:Npop dist(ic,1)=0; for id=1:Ncity dist(ic,1)=dist(ic)+dcity(tour(ic,id),tour(ic,id+1)); end % id end % ic
  1 Comment
Image Analyst
Image Analyst on 3 Jun 2015
The traveling salesman problem is not really related to the shortest path algorithm in imaging. TSP has to visit every node, in imaging we don't. I suggest you start your own question in a new discussion thread.

Sign in to comment.


Find more on Graph and Network Algorithms in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by