# Shortest Path in a 3D Matrix

32 views (last 30 days)
jan smith on 2 Jun 2015
Commented: Jurij Lorenzo Mazzola on 19 May 2022 at 13:36
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 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/

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

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 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.
Jurij Lorenzo Mazzola on 19 May 2022 at 13:36
Anyone has updates on the possibility to have a 'bwdistgeodesic' for 3D case?

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

### Community Treasure Hunt

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

Start Hunting!

Translated by