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[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:
  • MethodAutomaticmethod to use
  • Possible Method settings include "Dijkstra", "BellmanFord", and "UnitWeight".

Examples

open allclose all

Basic Examples  (1)

Give the distance for a grid graph:

Scope  (7)

GraphDistance works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Mixed graphs:

Use rules to specify the graph:

GraphDistance works with large graphs:

Options  (4)

Method  (4)

The method is automatically chosen, depending on input:

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

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

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

Applications  (5)

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

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

Visualize distance from a vertex in a tree:

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

Set color proportionally to distance:

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

Illustrate the DamerauLevenshteinDistance for short words over a small alphabet:

Find the Damerau–Levenshtein distance between two words:

Check the result:

Properties & Relations  (3)

The distance between two vertices can be found using FindShortestPath:

Distance matrix:

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

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

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_2021_graphdistance, author="Wolfram Research", title="{GraphDistance}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/GraphDistance.html}", note=[Accessed: 27-May-2022 ]}

BibLaTeX

@online{reference.wolfram_2021_graphdistance, organization={Wolfram Research}, title={GraphDistance}, year={2015}, url={https://reference.wolfram.com/language/ref/GraphDistance.html}, note=[Accessed: 27-May-2022 ]}