Effacer les filtres
Effacer les filtres

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

2 vues (au cours des 30 derniers jours)
Sim
Sim le 16 Déc 2022
Commenté : Jon le 16 Déc 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]}
  2 commentaires
Matt J
Matt J le 16 Déc 2022
Modifié(e) : Matt J le 16 Déc 2022
If there were a way, I think shortestpath() itself would already offer vectorized input/output, using that method.
Sim
Sim le 16 Déc 2022
Thanks @Matt J, Yes, I was thinking the same... :-)

Connectez-vous pour commenter.

Réponses (1)

Jon
Jon le 16 Déc 2022
Modifié(e) : Jon le 16 Déc 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 commentaires
Jon
Jon le 16 Déc 2022
The distances are, by definition, the shortest paths
Jon
Jon le 16 Déc 2022
So are you clear on this now, or would you like a further explanation

Connectez-vous pour commenter.

Catégories

En savoir plus sur Graph and Network Algorithms dans Help Center et File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by