shortest_path

Scilab function
Last update : 19/12/2005

shortest_path - chemin le plus court

### Calling Sequence

  `[p,lp] = shortest_path(i,j,g,[typ])`

### Parameters

- `i` : entier, numéro du sommet de départ
- `j` : entier, numéro du sommet d'arrivée
- `g` : graphe (liste)
- `typ` : chaîne de caractères, type du chemin le plus court
- `p` : vecteur ligne des numéros des arcs du chemin s'il existe
- `lp` : longueur du chemin

### Description

`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.

### Examples

    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';
               'Le nom des arcs peut être visualisé en selectionnant la valeur ""Name"" pour les arcs';
               'dans le menu Graph->Options.']);
    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);

### See Also

`find_path` , `nodes_2_path` ,