1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
shortest_path(1) Scilab function shortest_path(1)
NAME
shortest_path - shortest path
CALLING SEQUENCE
[p,lp] = shortest_path(i,j,g,[typ])
PARAMETERS
i : integer, number of start node
j : integer, number of end node
g : graph list
typ : string, type of shortest path
p : row vector of integer numbers of the arcs of the shortest path if it
exists
lp : length of shortest path
DESCRIPTION
shortest_path returns the shortest path p from node i to node j if it
exists, and the empty vector [] otherwise. The optional argument typ is a
string which defines the type of shortest path, 'arc' for the shortest path
with respect to the number of arcs and 'length' for the shortest path with
respect to the length of the edges edge_length.
For the shortest path with respect to the length of the edges, the lengths
are given by the element edge_length of the graph list. If its value is not
given (empty vector []), it is assumed to be equal to 0 on each edge.
Lengths can be positive, equal to 0 or negative.
When a shortest path exists, lp is the length of this path.
EXAMPLE
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(['Showing the arcs of the shortest path ';
'Choose ""Display arc names"" in the Graph menu to see arc names']);
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
|
