GraphTheory[AllPairsDistance] - Maple Help

Online Help

All Products    Maple    MapleSim


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 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 On3 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

withGraphTheory:

G:=Graph1,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 unweighted graph with 5 vertices and 8 edge(s)

(1)

AllPairsDistanceG

0111110121110121210111210

(2)

DiameterG

2

(3)

H:=Graphdirected,seq1,i,i=2..5,Trail2,3,4,5,2

H:=Graph 2: a directed unweighted graph with 5 vertices and 8 arc(s)

(4)

AllPairsDistanceH

01111∞0123∞3012∞2301∞1230

(5)

DrawGraphH

See Also

BellmanFordAlgorithm, Diameter, DijkstrasAlgorithm, Distance, Trail


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam