Network::allShortPath
--
shortest paths for all pairs of nodesNetwork::allShortPath
(G)
finds shortest
paths in the network G
.
Network::allShortPath(G <, Length>
<, Path>)
G |
- | network |
Length |
- | Return the lengths of shortest paths. This is the default unless Path is given. |
Path |
- | Return a table of shortest paths. |
A table or a sequence of two tables
Network::allShortPath
(G)
gives a table
with the length of a shortest path between two nodes i
and
j
for every i
and j
.Network::allShortPath
(G, Path)
returns a
table which contains a shortest path for every pair (i,j)
.
If there is no entry for a pair (i,j)
, then either
i=j
or j
cannot be reached from
i
in the network.Network::allShortPath
(G, Length)
returns
a table which contains the length of a shortest path for every pair
(i,j)
. The entry infinity
for
(i,j)
represents the fact, that j
cannot be
reached from i
in the network. If both Length and Path are specified, then
the distance table and the path table are returned. If the option Path is not given, the behaviour of
Network::allShortPath
with the option Length is the default behaviour.In a cyclic network with three vertices, each node can be reached in at most two steps.
>> N1 := Network::cycle([v1, v2, v3]): Network::allShortPath(N1)
table( (v3, v3) = 0, (v3, v2) = 2, (v3, v1) = 1, (v2, v3) = 1, (v2, v2) = 0, (v2, v1) = 2, (v1, v3) = 2, (v1, v2) = 1, (v1, v1) = 0 )
Adding a vertex which has no connection to the three
nodes, we get the expected entries infinity
. The table of paths
contains no entries referring to the newly added vertex.
>> N1 := Network::addVertex( N1, v4 ): Network::allShortPath(N1, Length, Path)
table( (v4, v4) = 0, (v4, v3) = infinity, (v4, v2) = infinity, (v4, v1) = infinity, (v3, v4) = infinity, table( (v3, v3) = 0, (v3, v2) = [v3, v1, v2], (v3, v2) = 2, (v3, v1) = [v3, v1], (v3, v1) = 1, , (v2, v3) = [v2, v3], (v2, v4) = infinity, (v2, v1) = [v2, v3, v1], (v2, v3) = 1, (v1, v3) = [v1, v2, v3], (v2, v2) = 0, (v1, v2) = [v1, v2] (v2, v1) = 2, ) (v1, v4) = infinity, (v1, v3) = 2, (v1, v2) = 1, (v1, v1) = 0 )
Network::AllShortPath