MATLAB Answers

Shortest path in a 2d matrix

71 views (last 30 days)
Vlad bibikov
Vlad bibikov on 20 Jan 2021
Edited: Bruno Luong on 27 Jan 2021
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?
  5 Comments
Walter Roberson
Walter Roberson on 27 Jan 2021
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.

Sign in to comment.

Accepted Answer

Bruno Luong
Bruno Luong on 27 Jan 2021
Edited: Bruno Luong on 27 Jan 2021
%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

More Answers (0)

Community Treasure Hunt

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

Start Hunting!

Translated by