Shortest path in a 2d matrix
8 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Vlad bibikov
le 20 Jan 2021
Modifié(e) : Bruno Luong
le 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 commentaires
Arpit Bhatia
le 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
le 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.
Réponse acceptée
Bruno Luong
le 27 Jan 2021
Modifié(e) : Bruno Luong
le 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
0 commentaires
Plus de réponses (0)
Voir également
Catégories
En savoir plus sur Graph and Network Algorithms dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!