Shortest path in a 2d matrix

5 Ansichten (letzte 30 Tage)
Vlad bibikov
Vlad bibikov am 20 Jan. 2021
Bearbeitet: Bruno Luong am 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 Kommentare
Arpit Bhatia
Arpit Bhatia am 27 Jan. 2021
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
Walter Roberson am 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.

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Bruno Luong
Bruno Luong am 27 Jan. 2021
Bearbeitet: Bruno Luong am 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

Weitere Antworten (0)

Kategorien

Mehr zu Graph and Network Algorithms finden Sie in Help Center und File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by