how to find kshortest path or use Dijkstra algorithm for 12 plot points.
3 次查看(过去 30 天)
显示 更早的评论
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/419948/image.jpeg)
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 个评论
Bruno Luong
2020-11-19
编辑:Bruno Luong
2020-11-19
The coordinates of ps/pg do not match (your data and your image). Possibly there are many other faulty data.
回答(3 个)
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
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/420523/image.png)
7 个评论
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)))
8 个评论
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));
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/419998/image.png)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Directed Graphs 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!