({{, (RefLink[GraphDistance, paclet:ref/GraphDistance])[g,s,t] 
gives the distance from source vertex s to target vertex t in the graph g.}, {, (RefLink[GraphDistance, paclet:ref/GraphDistance])[g,s]
gives the distance from s to all vertices of the graph g.}, {, (RefLink[GraphDistance, paclet:ref/GraphDistance])[{v->w,…},…]
uses rules v->w to specify the graph g.}})

OpenersNotesSection(Spacer1)Details and Options

(RefLink[GraphDistance, paclet:ref/GraphDistance])[g,s,t] will give the length of the shortest path between s and t.

The distance is (RefLink[Infinity, paclet:ref/Infinity]) when there is no path between s and t.

For a weighted graph, the distance is the minimum of the sum of weights along any path between s and t.

The following options can be given:

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

OpenersPrimaryExamplesSection(Spacer1)Examples  (20)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

Give the distance for a grid graph:

GraphDistance[,1,6]

OpenersExampleSection1(Spacer1)Scope  (7)

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

GraphDistance[,2,7]

Directed graphs:

GraphDistance[,1,4]

Weighted graphs:

GraphDistance[,2,3]

Multigraphs:

GraphDistance[,1,4]

Mixed graphs:

GraphDistance[,1,4]

Use rules to specify the graph:

GraphDistance[{1->2,2->3,3->1,3->4,4->5,3->5},1,4]

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

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

Timing[GraphDistance[g,1,10]]

OpenersExampleSection2(Spacer1)Options  (4)

OpenersExampleSubsection0(Spacer1)Method  (4)

The method is automatically chosen, depending on input:

{PetersenGraph[4,1,VertexSize->{1->Medium,7->Medium},PlotLabel->"Unweighted"],PetersenGraph[4,1,EdgeWeight->{4,0,3,1,3,2,7,8,5,2,1,6},VertexSize->{1->Medium,7->Medium},PlotLabel->"Weighted"]}

Table[GraphDistance[g,1,7],{g,%}]

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

GridGraph[{2,3},EdgeWeight->{5,2,2,5,1,2,2},VertexSize->{1->Small,5->Small}]

GraphDistance[%,1,5,Method->"UnitWeight"]

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

GridGraph[{2,3},EdgeWeight->{2,5,2,1,5,2,2},VertexSize->{1->Small,5->Small}]

GraphDistance[%,1,5,Method->"Dijkstra"]

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

WeightedAdjacencyGraph[(({{∞, 2, 5, ∞, ∞, ∞}, {∞, ∞, ∞, 2, ∞, ∞}, {∞, ∞, ∞, ∞, 5, ∞}, {∞, ∞, -2, ∞, ∞, 2}, {∞, ∞, ∞, ∞, ∞, ∞}, {∞, ∞, ∞, ∞, 2, ∞}})),VertexSize->{1->Small,5->Small},AbsoluteOptions[GridGraph[{2,3}],VertexCoordinates]]

GraphDistance[%,1,5,Method-> "BellmanFord"]

OpenersExampleSection3(Spacer1)Applications  (5)

Find the distance between opposite corners of a (RefLink[GridGraph, paclet:ref/GridGraph]) of size {6,6}:

GridGraph[{6,6},VertexSize->{1->Medium,(6^2)->Medium}]

GraphDistance[%,1,(6^2)]

Find the distance between opposite corners in a d-dimensional (RefLink[GridGraph, paclet:ref/GridGraph]) of size {6,6,…,6}:

TableForm[Table[{d,GraphDistance[GridGraph[ConstantArray[6,{d}]],1,(6^d)]},{d,2,6}],TableHeadings->{None,{"Dimension","Distance"}}]

Visualize distance from a vertex in a tree:

g=CompleteKaryTree[6,2,VertexSize->1]

Obtain the maximum distance from the vertex to any other vertex:

t=12;
max=VertexEccentricity[g,t]

Set color proportionally to distance:

HighlightGraph[g,Table[Style[s,GrayLevel[GraphDistance[g,s,t]/max]],{s,VertexList[g]}]]

The expected distance between two vertices for Bernoulli graphs with probability p is 2-p:

p=0.9;

Mean[GraphDistance[#,1,6]&/@RandomGraph[BernoulliGraphDistribution[9,p],2000]]//N

2-p

Illustrate the (RefLink[DamerauLevenshteinDistance, paclet:ref/DamerauLevenshteinDistance]) for short words over a small alphabet:

alphabet={"a","b","c"};
maxLen=4;

words=StringJoin@@#&/@Join@@Table[Tuples[alphabet,i],{i,1,maxLen}];

insertEdits[word_/;StringLength[word]≥maxLen]:={}

insertEdits[word_]:=Union@@Table[StringInsert[word,e,i],{e,alphabet},{i,1,Length[word]+1}]

substituteEdits[word_]:=Join@@Table[StringReplacePart[word,e,{i,i}],{i,1,StringLength[word]},{e,Select[alphabet,¬MatchQ[#,StringTake[word,{i}]]&]}]

transposeEdits[word_]:=Select[Table[StringJoin@@StringTake[word,{{1,i-1},{i+1},{i},{i+2,StringLength[word]}}],{i,1,StringLength[word]-1}],#≠word&]

edges=Union@@Join[Table[#\[UndirectedEdge]w,{w,Join@@Through[{insertEdits,substituteEdits,transposeEdits}[#]]}]&/@words,{SameTest->(Sort[List@@#1]===Sort[List@@#2]&)}];

g=Graph[words,edges]

Find the Damerau–Levenshtein distance between two words:

GraphDistance[g,"abc","cba"]

Check the result:

%==DamerauLevenshteinDistance["abc","cba"]

OpenersExampleSection4(Spacer1)Properties & Relations  (3)

The distance between two vertices can be found using (RefLink[FindShortestPath, paclet:ref/FindShortestPath]):

g=GridGraph[{3,4}]

FindShortestPath[g,1,12]

Length[%]-1

GraphDistance[g,1,12]

Distance matrix:

GraphDistanceMatrix[g][[1,12]]

In a connected graph, the (RefLink[VertexEccentricity, paclet:ref/VertexEccentricity]) can be computed using (RefLink[GraphDistance, paclet:ref/GraphDistance]):

g =GridGraph[{3,4}]

GraphDistance[g,1,#]&/@VertexList[g]

Max[%]

VertexEccentricity[g,1]

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

g=;

ConnectedGraphQ[g]

ConnectedComponents[g]

GraphDistance[g,3,5]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[GraphDistanceMatrix, paclet:ref/GraphDistanceMatrix])  ▪  (RefLink[BreadthFirstScan, paclet:ref/BreadthFirstScan])  ▪  (RefLink[DepthFirstScan, paclet:ref/DepthFirstScan])}})}})

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