Important: The networks package has been deprecated.  Use the superseding command GraphTheory[AllPairsDistance] instead.

This procedure is an implementation of Floyd's allpairs shortest path algorithm.

The result,  T, is a table of distances between any two vertices. Thus $T_{u,v}$ is the shortest distance from u to v.

The optional extra parameter (eg. parents) is used to supply a name for a table of ancestors.  Thus ${\mathrm{parents}}_{u,v}$ is the ancestor of v in the shortest path tree rooted at u.

Edge weights are assumed to be lengths or distances. Undirected edges are assumed to be bidirectional.

Edge weights must be non-negative.

This routine is normally loaded via the command with(networks) but may also be referenced using the full name networks[allpairs](...).

$\mathrm{with}\left(\mathrm{networks}\right)\:$

$G≔\mathrm{petersen}\left(\right)\:$

$T≔\mathrm{allpairs}\left(G\,p\right)\:$

$T\left[1,3\right]$

$2$

$p\left[1,3\right]$

$2$