GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/AllPairsDistance

GraphTheory

 AllPairsDistance

 Calling Sequence AllPairsDistance(G)

Parameters

 G - graph

Description

 • The AllPairsDistance command returns a square matrix A where ${A}_{i,j}$ is the distance from vertex i to vertex j in the graph G, that is, the length of the shortest path from vertex i to vertex j.  If G is not a weighted graph, then edges have weight 1. If there is no path, then the distance is infinite and ${A}_{i,j}=\mathrm{\infty }$.
 • This procedure is an implementation of the Floyd-Warshall all-pairs shortest path algorithm.  The complexity is $\mathrm{O}\left({n}^{3}\right)$ where n is the number of vertices of G.
 • To compute distances or shortest paths from a single vertex to every other vertex, use either DijkstrasAlgorithm or BellmanFordAlgorithm because they are more efficient.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{Graph}\left(\left[1,2,3,4,5\right],\left\{\left\{1,2\right\},\left\{1,3\right\},\left\{1,4\right\},\left\{1,5\right\},\left\{2,3\right\},\left\{3,4\right\},\left\{4,5\right\},\left\{5,2\right\}\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 5 vertices and 8 edge\left(s\right)}}$ (1)
 > $\mathrm{AllPairsDistance}\left(G\right)$
 $\left[\begin{array}{rrrrr}{0}& {1}& {1}& {1}& {1}\\ {1}& {0}& {1}& {2}& {1}\\ {1}& {1}& {0}& {1}& {2}\\ {1}& {2}& {1}& {0}& {1}\\ {1}& {1}& {2}& {1}& {0}\end{array}\right]$ (2)
 > $\mathrm{Diameter}\left(G\right)$
 ${2}$ (3)
 > $H≔\mathrm{Graph}\left(\mathrm{directed},\left\{\mathrm{seq}\left(\left[1,i\right],i=2..5\right)\right\},\mathrm{Trail}\left(2,3,4,5,2\right)\right)$
 ${H}{≔}{\mathrm{Graph 2: a directed unweighted graph with 5 vertices and 8 arc\left(s\right)}}$ (4)
 > $\mathrm{AllPairsDistance}\left(H\right)$
 $\left[\begin{array}{ccccc}{0}& {1}& {1}& {1}& {1}\\ {\mathrm{∞}}& {0}& {1}& {2}& {3}\\ {\mathrm{∞}}& {3}& {0}& {1}& {2}\\ {\mathrm{∞}}& {2}& {3}& {0}& {1}\\ {\mathrm{∞}}& {1}& {2}& {3}& {0}\end{array}\right]$ (5)
 > $\mathrm{DrawGraph}\left(H\right)$