Network::allShortPath --
shortest paths for all pairs of nodes
IntroductionNetwork::allShortPath(G) finds shortest
paths in the network G.
Call(s)Network::allShortPath(G <, Length>
<, Path>)
ParametersG |
- | network |
OptionsLength |
- | Return the lengths of shortest paths. This is the default unless Path is given. |
Path |
- | Return a table of shortest paths. |
ReturnsA table or a sequence of two tables
DetailsNetwork::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.
Example
1In 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
)
BackgroundNetwork::AllShortPath