The AllPairsDistance command returns a square matrix A where  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 .

This procedure is an implementation of the Floyd-Warshall all-pairs shortest path algorithm.  The complexity is  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.