# how to find kshortest path or use Dijkstra algorithm for 12 plot points.

조회 수: 8(최근 30일)
navanit dubey 2020년 11월 17일
댓글: navanit dubey 2020년 11월 20일
I have the xy coordinate for the source Ps and destination Pg and the other points
ps=[37 394];
pg=[383 123];
b1=[71 319];
b2=[105 379];
b3=[74 281];
b4=[340 339];
b5=[338 280];
b6=[48 125];
b7=[181 176];
b8=[197 176 ];
b9=[378 194];
b10=[341 112]
s = [1 1 3 2 4 4 7 8 5 6 6 9 10 11 ];
t = [ 2 3 5 4 7 8 8 9 6 9 10 11 12 12 ];
pos=[ps,b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,pg]
now I want them to find the shortest path for this nodes using Kshortest path yen algorithm
please tell me how to find it using these algorithm in this function
the point(440,440) is arbitary.
##### 댓글 수: 2표시숨기기 이전 댓글 수: 1
navanit dubey 2020년 11월 20일
yes Sir You are right , I had changed it in my codes but not here , wait I will change it now. Thankyou for pointing it out

댓글을 달려면 로그인하십시오.

### 답변(3개)

Walter Roberson 2020년 11월 19일
ps=[37 316];
pg=[382 471];
b1=[71 319];
b2=[105 379];
b3=[74 281];
b4=[340 339];
b5=[338 280];
b6=[48 125];
b7=[181 176];
b8=[197 176 ];
b9=[378 194];
b10=[341 112];
s = [1 1 3 2 4 4 7 8 5 6 6 9 10 11 ];
t = [ 2 3 5 4 7 8 8 9 6 9 10 11 12 12 ];
pos=[ps; b1; b2; b3; b4; b5; b6; b7; b8; b9; b10; pg];
weights = sqrt(sum((pos(s,:)-pos(t,:)).^2,2));
names = {'ps', 'b1', 'b2', 'b3', 'b4', 'b5', 'b6', 'b7', 'b8', 'b9', 'b10', 'pg'};
G = graph(s, t, weights, names);
plot(G)
strjoin(names(shortestpath(G, 1, 12)))
ans = 'ps b1 b3 b7 b8 b10 pg'
##### 댓글 수: 8표시숨기기 이전 댓글 수: 7
navanit dubey 2020년 11월 20일
Thankyou for the response sir, implimented it and its done.
code << labeledge(G,s,t,weights)

댓글을 달려면 로그인하십시오.

Christine Tobler 2020년 11월 19일
I'm not sure how the data you're adding here maps to the picture you attached. Here's how I would go about inserting the position and connectivity information you've given into a graph:
pos=[ps;b1;b2;b3;b4;b5;b6;b7;b8;b9;b10;pg];
G = graph(s, t);
plot(G, 'XData', pos(:, 1), 'YData', pos(:, 2));
##### 댓글 수: 1표시숨기기 없음
navanit dubey 2020년 11월 19일
Thankyou for the response , how should i implement it to get the shortest path of it.

댓글을 달려면 로그인하십시오.

Bruno Luong 2020년 11월 19일
편집: Bruno Luong 2020년 11월 20일
Assuming you want to find all paths from 1 to 12, using the code AllPath here, here is the 6 paths with the total distances (euclidian)
(1) -> (2) -> (4) -> (7) -> (8) -> (9) -> (6) -> (10) -> (12) (d=778.289)
(1) -> (2) -> (4) -> (7) -> (8) -> (9) -> (11) -> (12) (d=638.058)
(1) -> (2) -> (4) -> (8) -> (9) -> (6) -> (10) -> (12) (d=627.607)
(1) -> (2) -> (4) -> (8) -> (9) -> (11) -> (12) (d=487.377)
(1) -> (3) -> (5) -> (6) -> (9) -> (11) -> (12) (d=743.253)
(1) -> (3) -> (5) -> (6) -> (10) -> (12) (d=533.072)
Code
ps=[37 394];
pg=[383 123];
b1=[71 319];
b2=[105 379];
b3=[74 281];
b4=[340 339];
b5=[338 280];
b6=[48 125];
b7=[181 176];
b8=[197 176 ];
b9=[378 194];
b10=[341 112];
pos=[ps;b1;b2;b3;b4;b5;b6;b7;b8;b9;b10;pg];
s = [ 1 1 3 2 4 4 7 8 5 6 6 9 10 11 ];
t = [ 2 3 5 4 7 8 8 9 6 9 10 11 12 12 ];
% Euclidian distances
d = sqrt(sum((pos(s,:)-pos(t,:)).^2,2));
A = sparse(s, t, d, 12, 12);
A = A+A';
s = 1;
t = 12;
tempo = 1;
allp = AllPath(A, s, t);
PlotandAnimation(A, allp, tempo, pos);
%%
function PlotandAnimation(A, allp, tempo, pos)
n = size(A,1);
nodenames = arrayfun(@(i) sprintf('(%d)', i), 1:n, 'unif', 0);
% Plot and animation
figure
G = graph(A);
h = plot(G, 'XData', pos(:,1), 'YData', pos(:,2));
labelnode(h, 1:n, nodenames)
th = title('');
colormap([0.6; 0]*[1 1 1]);
E = table2array(G.Edges);
E = sort(E(:,1:2),2);
np = length(allp);
for k=1:np
pk = allp{k};
pkstr = nodenames(pk);
s = sprintf('%s -> ',pkstr{:});
s(end-3:end) = [];
i = sub2ind(size(A),pk(1:end-1),pk(2:end));
d = full(sum(A(i)));
fprintf('%s (d=%g)\n', s, d);
Ek = sort([pk(1:end-1); pk(2:end)],1)';
b = ismember(E, Ek, 'rows');
set(h, 'EdgeCData', b, 'LineWidth', 0.5+1.5*b);
set(th, 'String', sprintf('path %d/%d (d=%3.1f)', k, np, d));
pause(tempo);
end
end
##### 댓글 수: 7표시숨기기 이전 댓글 수: 6
navanit dubey 2020년 11월 20일
Ok Sir, Thankyou for the response.

댓글을 달려면 로그인하십시오.

### Community Treasure Hunt

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

Start Hunting!

Translated by