({{, (RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix])[g] 
gives the matrix of distances between vertices for the graph g.}, {, (RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix])[g,d]
gives the matrix of distances between vertices of maximal distance d in the graph g.}, {, (RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix])[{v->w,…},…]
uses rules v->w to specify the graph g.}})

OpenersNotesSection(Spacer1)Details and Options

(RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix]) returns a (RefLink[SparseArray, paclet:ref/SparseArray]) object or an ordinary matrix.

The entries of the distance matrix (Subscript[d, ij]) give the shortest distance from vertex (Subscript[v, i]) to vertex (Subscript[v, j]).

The diagonal entries (Subscript[d, ii]) of the distance matrix are always zero.

The entry (Subscript[d, ij]) is (RefLink[Infinity, paclet:ref/Infinity]) (∞) if there is no path from vertex (Subscript[v, i]) to vertex (Subscript[v, j]).

In (RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix])[g,d], an entry (Subscript[d, ij]) will be (RefLink[Infinity, paclet:ref/Infinity]) if there is no path from vertex (Subscript[v, i]) to vertex (Subscript[v, j]) in d steps or less.

The vertices (Subscript[v, i]) are assumed to be in the order given by (RefLink[VertexList, paclet:ref/VertexList])[g].

For a weighted graph, the distance is the minimum of the sum of weights along any path from vertex (Subscript[v, i]) to vertex (Subscript[v, j]).

The following options can be given:

Possible (RefLink[Method, paclet:ref/Method]) settings include "Dijkstra", "FloydWarshall", and "Johnson".

OpenersPrimaryExamplesSection(Spacer1)Examples  (25)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

Give the distance matrix for a Petersen graph:

GraphDistanceMatrix[]//MatrixForm

OpenersExampleSection1(Spacer1)Scope  (8)

(RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix]) works with undirected graphs:

GraphDistanceMatrix[]//MatrixForm

Directed graphs:

GraphDistanceMatrix[]//MatrixForm

Weighted graphs:

GraphDistanceMatrix[]//MatrixForm

Multigraphs:

GraphDistanceMatrix[]//MatrixForm

Mixed graphs:

GraphDistanceMatrix[]//MatrixForm

Use rules to specify the graph:

GraphDistanceMatrix[{1->2,2->3,3->1,3->4,4->5,3->5}]//MatrixForm

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

g=GridGraph[{10,10}];Timing[GraphDistanceMatrix[g][[All,1]]//Dimensions]

Using (RefLink[GraphDistance, paclet:ref/GraphDistance]) to compute the same result takes more time:

Timing[Table[GraphDistance[g,1,v],{v,VertexList[g]}]//Dimensions]

(RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix]) works with large graphs:

g=GridGraph[{10,10,10,10}];

Timing[GraphDistanceMatrix[g][[All,1]]//Dimensions]

When just a single column is needed and the graph is large, using (RefLink[GraphDistance, paclet:ref/GraphDistance]) is faster:

Timing[Table[GraphDistance[g,1,v],{v,VertexList[g]}]//Dimensions]

OpenersExampleSection2(Spacer1)Options  (6)

OpenersExampleSubsection0(Spacer1)Method  (6)

The method is automatically chosen depending on input:

{PetersenGraph[4,1,VertexShapeFunction->"Name"],PetersenGraph[4,1,EdgeWeight->{4,0,3,1,3,2,7,8,5,2,1,6},VertexShapeFunction->"Name"]}

Table[GraphDistanceMatrix[g]//MatrixForm,{g,%}]

"UnitWeight" method will use the weight 1 for every edge:

GridGraph[{2,3},EdgeWeight->{5,2,2,5,1,2,2},VertexShapeFunction->"Name"]

GraphDistanceMatrix[%,Method->"UnitWeight"]//MatrixForm

"Dijkstra" can be used for graphs with positive edge weights only:

GridGraph[{2,3},EdgeWeight->{5,2,2,5,1,2,2},VertexShapeFunction->"Name"]

GraphDistanceMatrix[%,Method->"Dijkstra"]//MatrixForm

"FloydWarshall" can be used for directed graphs including negative edge weights:

WeightedAdjacencyGraph[(({{∞, 2, 5, ∞, ∞, ∞}, {∞, ∞, ∞, 2, ∞, ∞}, {∞, ∞, ∞, ∞, 5, ∞}, {∞, ∞, -2, ∞, ∞, 2}, {∞, ∞, ∞, ∞, ∞, ∞}, {∞, ∞, ∞, ∞, 2, ∞}})),VertexShapeFunction->"Name",AbsoluteOptions[GridGraph[{2,3}],VertexCoordinates]]

GraphDistanceMatrix[%,Method->"FloydWarshall"]//MatrixForm

"Johnson" can be used for directed graphs including negative edge weights:

WeightedAdjacencyGraph[(({{∞, 2, 5, ∞, ∞, ∞}, {∞, ∞, ∞, 2, ∞, ∞}, {∞, ∞, ∞, ∞, 5, ∞}, {∞, ∞, -2, ∞, ∞, 2}, {∞, ∞, ∞, ∞, ∞, ∞}, {∞, ∞, ∞, ∞, 2, ∞}})),VertexShapeFunction->"Name",AbsoluteOptions[GridGraph[{2,3}],VertexCoordinates]]

GraphDistanceMatrix[%,Method->"Johnson"]//MatrixForm

"Johnson" can be faster than the "FloydWarshall" method on sparse graphs:

StarGraph[6,EdgeWeight->RandomReal[{1,5},5]]

GraphDistanceMatrix[%,Method->"Johnson"]//MatrixForm

OpenersExampleSection3(Spacer1)Applications  (2)

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

{a=PetersenGraph[7,2,VertexSize->{1->Medium}],b=Graph[Range[4],{1\[UndirectedEdge]2,3\[UndirectedEdge]4},VertexSize->{1->Medium}],c=Graph[Range[3],{1\[DirectedEdge]2,3\[DirectedEdge]2,3\[DirectedEdge]1},VertexSize->{1->Small},EdgeStyle->Arrowheads[Small]]}

Table[Max[GraphDistanceMatrix[g][[1]]],{g,{a,b,c}}]

For the strongly connected graph, the result is in agreement with (RefLink[VertexEccentricity, paclet:ref/VertexEccentricity]):

Table[VertexEccentricity[g,1],{g,{a,b,c}}]

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

g=GridGraph[{2,3,4}]

Max/@GraphDistanceMatrix[g]

Check the result:

%===Table[VertexEccentricity[g,v],{v,VertexList[g]}]

OpenersExampleSection4(Spacer1)Properties & Relations  (5)

Rows and columns of the distance matrix follow the order given by (RefLink[VertexList, paclet:ref/VertexList]):

g=;

VertexList[g]

TableForm[GraphDistanceMatrix[g],TableHeadings->{c=Style[#,Red]&/@%,c}]

The diagonal entries of the distance matrix are always zero:

PetersenGraph[5,2]

Diagonal[GraphDistanceMatrix[%]]

The distance matrix can be found using (RefLink[GraphDistance, paclet:ref/GraphDistance]):

g=GridGraph[{2,3}]

Table[GraphDistance[g,i,j],{i,VertexList[g]},{j,VertexList[g]}]==GraphDistanceMatrix[g]

In a connected graph, the (RefLink[VertexEccentricity, paclet:ref/VertexEccentricity]) can be obtained from the distance matrix:

g=GridGraph[{3,4}]

GraphDistanceMatrix[g][[VertexIndex[g,1],All]]//Max

VertexEccentricity[g,1]

The distance between two vertices belonging to different connected components is (RefLink[Infinity, paclet:ref/Infinity]):

g=;

ConnectedGraphQ[g]

GraphDistanceMatrix[g]//MatrixForm

OpenersExampleSection5(Spacer1)Possible Issues  (2)

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

g=Graph[{2\[UndirectedEdge]3,1\[UndirectedEdge]2},EdgeWeight->{1,10},VertexShapeFunction->"Name"]

(d=GraphDistanceMatrix[g])//MatrixForm

The distance from 2 to 3 is not at the expected matrix position:

GraphDistance[g,2,3]==d[[2,3]]

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

VertexList[g]

Solve the problem by listing vertices explicitly when calling functions such as (RefLink[Graph, paclet:ref/Graph]):

h=Graph[Range[3],{2\[UndirectedEdge]3,1\[UndirectedEdge]2},EdgeWeight->{1,10},VertexShapeFunction->"Name"]

VertexList[h]

GraphDistanceMatrix[h]//MatrixForm

Now the distance is found at the expected position:

GraphDistance[h,2,3]==%[[2,3]]

"BellmanFord" is not a valid (RefLink[Method, paclet:ref/Method]) option:

g=WeightedAdjacencyGraph[(({{∞, 2, 5, ∞, ∞, ∞}, {∞, ∞, ∞, 2, ∞, ∞}, {∞, ∞, ∞, ∞, 5, ∞}, {∞, ∞, -2, ∞, ∞, 2}, {∞, ∞, ∞, ∞, ∞, ∞}, {∞, ∞, ∞, ∞, 2, ∞}})),VertexShapeFunction->"Name",AbsoluteOptions[GridGraph[{2,3}],VertexCoordinates]]

GraphDistanceMatrix[g,Method->"BellmanFord"]//MatrixForm

Use "FloydWarshall", "Johnson", or the default choice of (RefLink[Method, paclet:ref/Method]) instead:

GraphDistanceMatrix[g,Method->"FloydWarshall"]//MatrixForm

GraphDistanceMatrix[g,Method->"Johnson"]//MatrixForm

GraphDistanceMatrix[g]//MatrixForm

OpenersExampleSection6(Spacer1)Neat Examples  (1)

MatrixPlot[GraphDistanceMatrix[GridGraph[{20,20}]]]

MatrixPlot[GraphDistanceMatrix[KnightTourGraph[20,20]]]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[GraphDistance, paclet:ref/GraphDistance])  ▪  (RefLink[AdjacencyMatrix, paclet:ref/AdjacencyMatrix])  ▪  (RefLink[GraphPower, paclet:ref/GraphPower])  ▪  (RefLink[GraphRadius, paclet:ref/GraphRadius])  ▪  (RefLink[GraphDiameter, paclet:ref/GraphDiameter])  ▪  (RefLink[GraphCenter, paclet:ref/GraphCenter])  ▪  (RefLink[GraphPeriphery, paclet:ref/GraphPeriphery])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Paths, Cycles, and Flows, paclet:guide/GraphPathsCyclesAndFlows])}, {▪(RefLinkPlain[Graph Measures & Metrics, paclet:guide/GraphMeasures])}, {▪(RefLinkPlain[Graph Properties & Measurements, paclet:guide/GraphPropertiesAndMeasurements])}})}})