## `Network::allShortPath` -- shortest paths for all pairs of nodes

#### Introduction

`Network::allShortPath``(G)` finds shortest paths in the network `G`.

#### Call(s)

`Network::allShortPath(G <, Length> <, Path>)`

#### Parameters

`G` | - | network

#### Options

`Length` | - | Return the lengths of shortest paths. This is the default unless Path is given.
`Path` | - | Return a table of shortest paths.

#### Returns

A table or a sequence of two tables

#### Details

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

#### Example 1

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
                )

#### Background

- The implemented algorithm is taken from Floyd, "Algorithm 97, Shortest Path", Comm. ACM, Vol. 5, 1962. The running time is O(n3), where n is the number of nodes.

#### Changes

- used to be called `Network::AllShortPath`

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000