Shortest Path in a 3D Matrix

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.

[James Tursa]

Define shortest path. What about ties?

[jan smith]

From one point to another I can move in any direction going through the nearest neighbors. Each element in the matrix has 26 neighbors. The shortest path contains the lowest number of elements.

[Alfonso Nieto-Castanon]

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]

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/

Answer 1

[Alfonso Nieto-Castanon]

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

[Walter Roberson]

Hmmm? Your code doesn't appear to be dodging around holes at all. You calculate "i" without regard to the content of BW and then say how many 1's were in the path. The user's question is a path-finding question, where you have to follow only the 1's to get between locations. (They were not specific as to whether diagonal moves are permitted.)

[Alfonso Nieto-Castanon]

sorry if I misinterpreted, I saw no explicit mention of only 1's allowed in the path; I took this

"check how many elements with 1 are in the path"

to mean that the path may contain 1's or 0's, and this

"From one point to another I can move in any direction going through the nearest neighbors. Each element in the matrix has 26 neighbors"

to mean that diagonals are allowed...

In any way, you are right that only allowing movement through 1's would make this a more interesting problem. If that is the case please disregard this answer.

[jan smith]

Thanks a lot. It was what I was looking for.

[Alfonso Nieto-Castanon]

Excellent, happy to help (and happy to hear I was not misinterpreting).

Finally, just for completion, if only allowed to walk through 1's, then you could use something like this instead:

 init = [nan inf];
 D = repmat(init(1+BW),[1 1 1 2]);
 D(i1(1),i1(2),i1(3),1) = 0;
 D(i2(1),i2(2),i2(3),2) = 0;
 mask = D==0;
 n = 0;
 while isinf(D(i2(1),i2(2),i2(3)))&nnz(mask),
   n = n+1;
   mask = convn(mask,ones([3 3 3]),'same')&isinf(D);
   D(mask) = n;
 end
 if isinf(D(i2(1),i2(2),i2(3)))
   error('no path found');
 else
   mask = sum(D,4)==n; % points within minimum-length path(s)
   sumBW = sum(BW(mask));
 end

You would still have to define what to do about multiple minimum-length paths (in the example above we are simply including all points that belong to any minimum-length path between the initial and end points)

[ROY EL ZEGHONDI]

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]

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.

Answer 2

[Walter Roberson]

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

Answer 3

[Image Analyst]

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.

[Walter Roberson]

bwdistgeodesic is not documented as working on 3D images. In particular the description of how it works is in terms of 2D.

[Alex Taylor]

bwdistgeodesic does work on 3-D data.

[Image Analyst]

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.

Answer 4

[ahmad karim]

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]

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.