Shortest path in a 2d matrix

10 次查看（过去 30 天）
Vlad bibikov
Vlad bibikov 2021-1-20
编辑： Bruno Luong 2021-1-27
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 个评论
显示 3更早的评论
Arpit Bhatia
Arpit Bhatia 2021-1-27
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 2021-1-27
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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Bruno Luong
Bruno Luong 2021-1-27
编辑：Bruno Luong 2021-1-27
%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 个）

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by