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

14 ビュー (過去 30 日間)
navanit dubey
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 件のコメント
navanit dubey
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 件)

Bruno Luong
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 件のコメント
navanit dubey
navanit dubey 2020 年 11 月 20 日
Ok Sir, Thankyou for the response.

サインインしてコメントする。


Walter Roberson
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 件のコメント
navanit dubey
navanit dubey 2020 年 11 月 20 日
Thankyou for the response sir, implimented it and its done.
code << labeledge(G,s,t,weights)

サインインしてコメントする。


Christine Tobler
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
navanit dubey 2020 年 11 月 19 日
編集済み: navanit dubey 2020 年 11 月 19 日
Thankyou for the response , how should i implement it to get the shortest path of it.

サインインしてコメントする。

カテゴリ

Find more on Graphics Objects in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by