shortest_path - chemin le plus court
shortest_path renvoie le chemin le plus court p du sommet i au sommet j s'il existe, et le vecteur vide [] sinon. L'argument optionnel typ est une chaîne définissant le type du chemin, 'arc' pour le chemin le plus court par rapport au nombre d'arcs et 'length' pour le chemin le plus court par rapport à la longueur des arêtes edge_length .
Pour le chemin le plus court par rapport à la longueur des arêtes, les longueurs sont données par les éléments edge_length du graphe. Si cette valeur n'est pas donnée (vecteur vide [] ), elle est supposée nulle sur chaque arête. Les longueurs peuvent être positives ou négatives (ou nulles).
Quand le chemin le plus court existe, lp est la longueur du chemin.
ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 181 276 278 276 103 174 281 177 86 175 90 290 397 399];
show_graph(g);
g1=g;ma=prod(size(g1('head')));
rand('uniform');
g1('edge_length')=int(20*rand(1,ma));
[p,lp]=shortest_path(13,1,g1,'length');
p
x_message(['Voici le chemin le plus court';
'Choisissez ""Display arc names"" dans le menu Graph pour voir les noms des arcs']);
g1('edge_name')=string(g1('edge_length'));
edgecolor=ones(1:ma);edgecolor(p)=11*ones(p);
g1('edge_color')=edgecolor;
edgefontsize=12*ones(1,ma);edgefontsize(p)=18*ones(p);
g1('edge_font_size')=edgefontsize;
show_graph(g1);