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

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

https://in.mathworks.com/matlabcentral/fileexchange/32513-k-shortest-path-yen-s-algorithm?s_tid=srchtitle

the point(440,440) is arbitary.

[Bruno Luong]

The coordinates of ps/pg do not match (your data and your image). Possibly there are many other faulty data.

[navanit dubey]

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

Answer 1

[Bruno Luong]

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

[navanit dubey]

Thankyou so much for the effort sir.It helped me a lot.

[navanit dubey]

Sr, how should I change the label NaN connected???

[Bruno Luong]

Code edited with data corrected and change label

[navanit dubey]

Thankyou, Sir

[navanit dubey]

Sir, I have a doubt , for shortest path I saw some use map or load matrix like here https://github.com/petercorke/robotics-toolbox-matlab/blob/master/Bug2.m

in my code how should I get the matrix to load the map?

[Bruno Luong]

I have no comment in other people's code.

[navanit dubey]

Ok Sir, Thankyou for the response.

Answer 2

[Walter Roberson]

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'

[navanit dubey]

Thankyou so much sir , I will implement it to my code.

[navanit dubey]

Sir, it worked perfectly fine with it and by using the euclidean distance too it got right, sir can you suggest me some ways where I can get short as well as multiple path from ps to pg.

Thankyou for the reply sir.

[Walter Roberson]

https://www.mathworks.com/matlabcentral/answers/171277-how-can-i-get-all-paths-between-two-nodes#answer_165813

[Walter Roberson]

Christine's XData and YData on the plot() call is a good addition.

[navanit dubey]

Thankyou for the response sir, will look to it and work on it.

[navanit dubey]

Sir is there a way to show the distance on the graph

node_distance =[69.69 82.34 238.38 38.12 158.15 149.91 142.44 16 59.04 175.21 94.85 157.58 71.18 43.42]

[Walter Roberson]

https://www.mathworks.com/help/matlab/math/graph-plotting-and-customization.html?s_tid=answers_rc2-2_p5_MLT#GraphPlotCustomizationExampleSectionsExample-7 shows labeling edges

[navanit dubey]

Thankyou for the response sir, implimented it and its done.

code << labeledge(G,s,t,weights)

Answer 3

[Christine Tobler]

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));

[navanit dubey]

Thankyou for the response , how should i implement it to get the shortest path of it.