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: an undirected unweighted graph with 5 vertices and 8 edge(s)
H≔Graph 2: a directed unweighted graph with 5 vertices and 8 arc(s)
Download Help Document
What kind of issue would you like to report? (Optional)