Shortest path in a 2d matrix

Hello, i have 2d n*n random matrix. I need to find the shortest way from one matrix element on the edge to another element on the edge of field. I tried to use a* and dijkstra methods, but its based on graphs. Is there any ways to convert 2d matrix into graph or other ways to solve this problem?

[Walter Roberson]

Do the values represent weights of some kind? "shortest path" algorithms traditionally associate cost with edges, not with nodes.

Should we be assuming 4 connectivity or 8 connectivity?

Does the number associated with the first node count as part of the total?

[Adam Danz]

There are a plethora of shortest-path solutions in this forum. Here's a relatively recent blog post that might help, too.

https://blogs.mathworks.com/steve/2011/12/13/exploring-shortest-paths-part-5/

[Vlad bibikov]

Walter Roberson yes, values represent weights. From the start point you can move only in 4 directions. And the number associated with the first node(start point) does count as part of the total. For example, we have

[ 1 2 3;

4 5 6;

7 8 9 ]

And now we are going to find the shortest path from 2 to 7. it will be 1 - 4 - 7 and so on

[Arpit Bhatia]

Hi Vlad,

You need to consider the matrix as the weighted adjacency matrix of a graph and then run the the shortest path algorithms on it. The following resource should help you better understand the adjacency matrix representation: http://users.monash.edu/~lloyd/tildeAlgDS/Graph/

[Walter Roberson]

Using the matrix directly as a weighted adjacency matrix does not work. Adjacency matrices represent costs for transitioning edges --- for example adj(3,2) is the cost for moving from node 3 to node 2. But the 2D array being discussed is a cost associated with visiting a node no matter how you got there so you have to synthesize several edges all with the same cost

ABCD
EFGH
IJKL

with 4 connection, the cost at F becomes the cost for traveling B'E' or B'G' or B'J', or E'B' or E'G' or E'J', or G'B' or G'E' or G'J', or J'B' or J'E' or J'G' where the ' here stands for "outside" of -- if you travel B'->E' through F cost, then you have not yet accounted for the cost of having visited B or arriving at E. Then if you did B'(F)E' then you have to consider the cost of F'(E)* nodes such as F'(E)A' F'(E)I' -- notice that the node you are "starting at" is not the same one as you just "arrived at" when you traveled B'(F)E' but next node has to be F'(E) something...

In terms of graph theory, you need to take the "dual" of the graph implied by the adjacency matrix, turning the edges into nodes and the nodes into edges.

Answer 1

[Bruno Luong]

%W=[ 1 2 3;
% 4 5 6;
% 7 8 9 ]
W = randi(9,5,5)

% Build the 4-connected graph
[m, n] = size(W);
[i, j] = ndgrid(1:m,1:n);

s2i = @(i,j) sub2ind(size(W),i,j);
s = s2i(i,j);

b1 = j>1;
s1 = s(b1);
d1 = s2i(i(b1),j(b1)-1);

b2 = j<n;
s2 = s(b2);
d2 = s2i(i(b2),j(b2)+1);

b3 = i>1;
s3 = s(b3);
d3 = s2i(i(b3)-1,j(b3));

b4 = i<m;
s4 = s(b4);
d4 = s2i(i(b4)+1,j(b4));

s = [s1 s2 s3 s4];
d = [d1 d2 d3 d4];
w = W(d);

G = digraph(s, d, w);
start   = [1, 1]; % the start indices coordinates, upper-left
stop    = [m, n];  % the stop indices coordinates, lower-right

% Find the shorttest path
k = G.shortestpath(s2i(start(1),start(2)), s2i(stop(1),stop(2)));
k = k(:);
[i,j] = ind2sub(size(W),k);
cost = W(k);

% Display result
stpath = table(i,j,cost)

You 'll get

W =

     7     7     8     4     5
     7     1     7     4     5
     4     3     3     7     6
     6     1     9     8     7
     2     1     1     2     7


stpath =

  9×3 table

    i    j    cost
    _    _    ____

    1    1     7  
    2    1     7  
    2    2     1  
    3    2     3  
    4    2     1  
    5    2     1  
    5    3     1  
    5    4     2  
    5    5     7