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

2 views (last 30 days)
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 Comments
Bruno Luong
Bruno Luong on 19 Nov 2020
Edited: Bruno Luong on 19 Nov 2020
The coordinates of ps/pg do not match (your data and your image). Possibly there are many other faulty data.
navanit dubey
navanit dubey on 20 Nov 2020
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

Sign in to comment.

Answers (3)

Bruno Luong
Bruno Luong on 19 Nov 2020
Edited: Bruno Luong on 20 Nov 2020
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 Comments

Sign in to comment.


Walter Roberson
Walter Roberson on 19 Nov 2020
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 Comments
navanit dubey
navanit dubey on 20 Nov 2020
Thankyou for the response sir, implimented it and its done.
code << labeledge(G,s,t,weights)

Sign in to comment.


Christine Tobler
Christine Tobler on 19 Nov 2020
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 Comment
navanit dubey
navanit dubey on 19 Nov 2020
Edited: navanit dubey on 19 Nov 2020
Thankyou for the response , how should i implement it to get the shortest path of it.

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!