BUILT-IN MATHEMATICA SYMBOL

GraphDistanceMatrix

GraphDistanceMatrix[g]
gives the matrix of distances between vertices for the graph g.

GraphDistanceMatrix

gives the matrix of distances between vertices of maximal distance d in the graph g.

MORE INFORMATION

GraphDistanceMatrix returns a SparseArray object or an ordinary matrix.

The entries of the distance matrix give the shortest distance from vertex to vertex .

The diagonal entries of the distance matrix are always zero.

The entry is Infinity () if there is no path from vertex to vertex .

In GraphDistanceMatrix, an entry will be Infinity if there is no path from vertex to vertex in d steps or less.

The vertices are assumed to be in the order given by VertexList[g].

EXAMPLES

CLOSE ALL

Basic Examples (1)

Give the matrix of distances for a complete graph:

In[1]:=

Out[1]=

In[2]:=

Out[2]//MatrixForm=

Scope (5)

GraphDistanceMatrix works with undirected graphs:

Directed graphs:

Weighted graphs:

Extract a single matrix column for a graph of modest size:

Using GraphDistance to compute the same result takes more time:

Works with large graphs:

When just a single column is needed and the graph is large, using GraphDistance is faster:

Options (6)

The method is automatically chosen depending on input:

method will use the weight 1 for every edge:

can be used for graphs with positive edge weights only:

can be used for directed graphs including negative edge weights:

can be faster than the

method on sparse graphs:

Applications (2)

Find the vertex eccentricity, taking the entire graph into account:

For the strongly connected graph, the result is in agreement with VertexEccentricity:

Find the vertex eccentricity of every vertex in a connected graph:

Check the result:

Properties & Relations (5)

Rows and columns of the distance matrix follow the order given by VertexList:

The diagonal entries of the distance matrix are always zero:

The distance matrix can be found using GraphDistance:

In a connected graph, the VertexEccentricity can be obtained from the distance matrix:

The distance between two vertices belonging to different connected components is Infinity:

Possible Issues (2)

The matrix indices may not have the expected correspondence to vertices:

The distance from

to

is not at the expected matrix position:

The reason is that vertices are not in the expected order:

Solve the problem by listing vertices explicitly when calling functions such as Graph:

Now the distance is found at the expected position:

is not a valid Method option:

Use

,

, or the default choice of Method instead:

Neat Examples (1)