WOLFRAM

Wolfram Language & System Documentation Center

GraphDistance[g,s,t]

gives the distance from source vertex s to target vertex t in the graph g.

GraphDistance[g,s]

gives the distance from s to all vertices of the graph g.

GraphDistance[{vw,…},…]

uses rules vw to specify the graph g.

Details and Options
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Options  
Method  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

GraphDistance

GraphDistance[g,s,t]

gives the distance from source vertex s to target vertex t in the graph g.

GraphDistance[g,s]

gives the distance from s to all vertices of the graph g.

GraphDistance[{vw,…},…]

uses rules vw to specify the graph g.

Details and Options

  • GraphDistance is also known as geodesic distance.
  • GraphDistance[g,s,t] will give the length of the shortest path between s and t.
  • The distance is 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:
  • Method Automaticmethod to use
  • Possible Method settings include "Dijkstra", "BellmanFord", and "UnitWeight".

Examples

open all close all

Basic Examples  (1)

Give the distance for a grid graph:

Wolfram Language code: GraphDistance[[image], 1, 6]

Scope  (7)

GraphDistance works with undirected graphs:

Wolfram Language code: GraphDistance[[image], 2, 7]

Directed graphs:

Wolfram Language code: GraphDistance[[image], 1, 4]

Weighted graphs:

Wolfram Language code: GraphDistance[[image], 2, 3]

Multigraphs:

Wolfram Language code: GraphDistance[[image], 1, 4]

Mixed graphs:

Wolfram Language code: GraphDistance[[image], 1, 4]

Use rules to specify the graph:

Wolfram Language code: GraphDistance[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 4 -> 5, 3 -> 5}, 1, 4]

GraphDistance works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: Timing[GraphDistance[g, 1, 10]]

Options  (4)

Method  (4)

The method is automatically chosen, depending on input:

Wolfram Language code: {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"]}
Wolfram Language code: Table[GraphDistance[g, 1, 7], {g, %}]

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

Wolfram Language code: GridGraph[{2, 3}, EdgeWeight -> {5, 2, 2, 5, 1, 2, 2}, VertexSize -> {1 -> Small, 5 -> Small}]
Wolfram Language code: GraphDistance[%, 1, 5, Method -> "UnitWeight"]

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

Wolfram Language code: GridGraph[{2, 3}, EdgeWeight -> {2, 5, 2, 1, 5, 2, 2}, VertexSize -> {1 -> Small, 5 -> Small}]
Wolfram Language code: GraphDistance[%, 1, 5, Method -> "Dijkstra"]

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

Wolfram Language code: WeightedAdjacencyGraph[(| | | | | | | | - | - | -- | - | - | - | | ∞ | 2 | 5 | ∞ | ∞ | ∞ | | ∞ | ∞ | ∞ | 2 | ∞ | ∞ | | ∞ | ∞ | ∞ | ∞ | 5 | ∞ | | ∞ | ∞ | -2 | ∞ | ∞ | 2 | | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | | ∞ | ∞ | ∞ | ∞ | 2 | ∞ |), VertexSize -> {1 -> Small, 5 -> Small}, AbsoluteOptions[GridGraph[{2, 3}], VertexCoordinates]]
Wolfram Language code: GraphDistance[%, 1, 5, Method -> "BellmanFord"]

Applications  (5)

Find the distance between opposite corners of a GridGraph of size {6,6}:

Wolfram Language code: GridGraph[{6, 6}, VertexSize -> {1 -> Medium, 6^2 -> Medium}]
Wolfram Language code: GraphDistance[%, 1, 6^2]

Find the distance between opposite corners in a -dimensional GridGraph of size {6,6,…,6}:

Wolfram Language code: 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:

Wolfram Language code: g = CompleteKaryTree[6, 2, VertexSize -> 0.5]

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

Wolfram Language code: t = 12; max = VertexEccentricity[g, t]

Set color proportionally to distance:

Wolfram Language code: 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 is :

Wolfram Language code: p = 0.9;
Wolfram Language code: Mean[GraphDistance[#, 1, 6]& /@ RandomGraph[BernoulliGraphDistribution[9, p], 2000]]//N
Wolfram Language code: 2 - p

Illustrate the DamerauLevenshteinDistance for short words over a small alphabet:

Wolfram Language code: alphabet = {"a", "b", "c"}; maxLen = 4;
Wolfram Language code: words = StringJoin@@#& /@ Join@@Table[Tuples[alphabet, i], {i, 1, maxLen}];
Wolfram Language code: insertEdits[word_ /; StringLength[word] ≥ maxLen] := {}
Wolfram Language code: insertEdits[word_] := Union@@Table[StringInsert[word, e, i], {e, alphabet}, {i, 1, Length[word] + 1}]
Wolfram Language code: substituteEdits[word_] := Join@@Table[StringReplacePart[word, e, {i, i}], {i, 1, StringLength[word]}, {e, Select[alphabet, ¬MatchQ[#, StringTake[word, {i}]]&]}]
Wolfram Language code: transposeEdits[word_] := Select[Table[StringJoin@@StringTake[word, {{1, i - 1}, {i + 1}, {i}, {i + 2, StringLength[word]}}], {i, 1, StringLength[word] - 1}], # ≠ word&]
Wolfram Language code: edges = Union@@Join[Table[#w, {w, Join@@Through[{insertEdits, substituteEdits, transposeEdits}[#]]}]& /@ words, {SameTest -> (Sort[List@@#1] === Sort[List@@#2]&)}];
Wolfram Language code: g = Graph[words, edges]

Find the Damerau–Levenshtein distance between two words:

Wolfram Language code: GraphDistance[g, "abc", "cba"]

Check the result:

Wolfram Language code: % == DamerauLevenshteinDistance["abc", "cba"]

Properties & Relations  (3)

The distance between two vertices can be found using FindShortestPath:

Wolfram Language code: g = GridGraph[{3, 4}]
Wolfram Language code: FindShortestPath[g, 1, 12]
Wolfram Language code: Length[%] - 1
Wolfram Language code: GraphDistance[g, 1, 12]

Distance matrix:

Wolfram Language code: GraphDistanceMatrix[g][[1, 12]]

In a connected graph, the VertexEccentricity can be computed using GraphDistance:

Wolfram Language code: g = GridGraph[{3, 4}]
Wolfram Language code: GraphDistance[g, 1, #]& /@ VertexList[g]
Wolfram Language code: Max[%]
Wolfram Language code: VertexEccentricity[g, 1]

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

Wolfram Language code: g = [image];
Wolfram Language code: ConnectedGraphQ[g]
Wolfram Language code: ConnectedComponents[g]
Wolfram Language code: GraphDistance[g, 3, 5]
Wolfram Research (2010), GraphDistance, Wolfram Language function, https://reference.wolfram.com/language/ref/GraphDistance.html (updated 2015).

Text

Wolfram Research (2010), GraphDistance, Wolfram Language function, https://reference.wolfram.com/language/ref/GraphDistance.html (updated 2015).

CMS

Wolfram Language. 2010. "GraphDistance." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/GraphDistance.html.

APA

Wolfram Language. (2010). GraphDistance. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/GraphDistance.html

BibTeX

@misc{reference.wolfram_2026_graphdistance, author="Wolfram Research", title="{GraphDistance}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/GraphDistance.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_graphdistance, organization={Wolfram Research}, title={GraphDistance}, year={2015}, url={https://reference.wolfram.com/language/ref/GraphDistance.html}, note=[Accessed: 12-June-2026]}