Shortest Path in a 3D Matrix
3 views (last 30 days)
Show older comments
jan smith
on 2 Jun 2015
Commented: Marta Alcalde
on 28 Jun 2022
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.
4 Comments
Alfonso Nieto-Castanon
on 2 Jun 2015
that definition does not lead to unique trajectories. Consider in 2d-space:
0 0 1 2 3 0
0 0 0 0 0 4
or
0 0 1 0 0 0
0 0 0 2 3 4
or
0 0 1 2 0 0
0 0 0 0 3 4
all have the same number of elements. What should the algorithm do with these multiple optimal paths?
Image Analyst
on 2 Jun 2015
Steve talks about the non-uniqueness of paths in part 2 of his blog: http://blogs.mathworks.com/steve/2011/11/26/exploring-shortest-paths-part-2/
Accepted Answer
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
6 Comments
ROY EL ZEGHONDI
on 23 Sep 2020
this worked for me, and i think i understand the general idea behind it but if possible can u explain how the steps work ?
thank you
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.
More Answers (3)
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.
0 Comments
Image Analyst
on 2 Jun 2015
Steve has a blog on that: http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/ though I don't know if bwdistgeodesic works on 3D images.
3 Comments
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.
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
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.
See Also
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!