61 views (last 30 days)

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

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

Start Hunting!
## 5 Comments

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1275468

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1275468

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1275543

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1275543

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1277253

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1277253

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1288933

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1288933

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1289003

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722518-shortest-path-in-a-2d-matrix#comment_1289003

Sign in to comment.