# Get shortest paths and distances among nodes without loop for (and possibly in a faster way)

2 views (last 30 days)
Sim on 16 Dec 2022
Commented: Jon on 16 Dec 2022
How to get shortest paths and distances among nodes (selected from a list) without a loop for, and possibly in a faster way than what shown in the following example ?
% Input 1 (the graph)
s = [1 1 1 1 2 2 2 2 2 8 8 12 14 14 1 14];
t = [3 5 4 2 6 10 7 9 8 11 12 13 7 6 8 15];
G = graph(s,t);
plot(G)
% Input 2 (list of nodes, among which, both shortest paths and distances will be
% calculated)
list = [3 7 8 9 10 14];
% Calculation
tic
for i = 1 :length(list)
for j = 1 : length(list)
[p,d] = shortestpath(G,list(i),list(j));
nodes_path{i,j} = p;
nodes_distances{i,j} = d;
end
end
toc
Elapsed time is 0.016856 seconds.
% Outputs
nodes_path,
nodes_path = 6×6 cell array
{[ 3]} {[3 1 2 7]} {[ 3 1 8]} {[ 3 1 2 9]} {[ 3 1 2 10]} {[3 1 2 6 14]} {[ 7 2 1 3]} {[ 7]} {[ 7 2 8]} {[ 7 2 9]} {[ 7 2 10]} {[ 7 14]} {[ 8 1 3]} {[ 8 2 7]} {[ 8]} {[ 8 2 9]} {[ 8 2 10]} {[ 8 2 6 14]} {[ 9 2 1 3]} {[ 9 2 7]} {[ 9 2 8]} {[ 9]} {[ 9 2 10]} {[ 9 2 6 14]} {[ 10 2 1 3]} {[ 10 2 7]} {[ 10 2 8]} {[ 10 2 9]} {[ 10]} {[ 10 2 6 14]} {[14 6 2 1 3]} {[ 14 7]} {[14 6 2 8]} {[14 6 2 9]} {[14 6 2 10]} {[ 14]}
nodes_distances,
nodes_distances = 6×6 cell array
{[0]} {[3]} {[2]} {[3]} {[3]} {[4]} {[3]} {[0]} {[2]} {[2]} {[2]} {[1]} {[2]} {[2]} {[0]} {[2]} {[2]} {[3]} {[3]} {[2]} {[2]} {[0]} {[2]} {[3]} {[3]} {[2]} {[2]} {[2]} {[0]} {[3]} {[4]} {[1]} {[3]} {[3]} {[3]} {[0]}
Matt J on 16 Dec 2022
Edited: Matt J on 16 Dec 2022
If there were a way, I think shortestpath() itself would already offer vectorized input/output, using that method.
Sim on 16 Dec 2022
Thanks @Matt J, Yes, I was thinking the same... :-)

Jon on 16 Dec 2022
Edited: Jon on 16 Dec 2022
for the distances (shortest path) between every pair of nodes in the graph
d = distances(G)
and for some subset, in your case list
d = distances(G,list,list)
##### 3 CommentsShow 1 older commentHide 1 older comment
Jon on 16 Dec 2022
The distances are, by definition, the shortest paths
Jon on 16 Dec 2022
So are you clear on this now, or would you like a further explanation