all-pairs shortest paths in a graph
The AllPairsDistance command returns a square matrix A where Ai,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 Ai,j=∞.
This procedure is an implementation of the Floyd-Warshall all-pairs shortest path algorithm. The complexity is O⁡n3 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.
G ≔ Graph⁡1,2,3,4,5,1,2,1,3,1,4,1,5,2,3,3,4,4,5,5,2
G≔Graph 1: an undirected graph with 5 vertices and 8 edge(s)
H ≔ Graph⁡directed,seq⁡1,i,i=2..5,Trail⁡2,3,4,5,2
H≔Graph 2: a directed graph with 5 vertices and 8 arc(s)
Download Help Document