how to find kshortest path or use Dijkstra algorithm for 12 plot points.
14 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
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 Kommentare
Bruno Luong
am 19 Nov. 2020
Bearbeitet: Bruno Luong
am 19 Nov. 2020
The coordinates of ps/pg do not match (your data and your image). Possibly there are many other faulty data.
Antworten (3)
Bruno Luong
am 19 Nov. 2020
Bearbeitet: Bruno Luong
am 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 Kommentare
Walter Roberson
am 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)))
8 Kommentare
Christine Tobler
am 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 Kommentar
Siehe auch
Kategorien
Mehr zu Directed Graphs finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!