# 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 Automatic method 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 DamerauLevenshtein 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_2024_graphdistance, author="Wolfram Research", title="{GraphDistance}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/GraphDistance.html}", note=[Accessed: 29-May-2024 ]}

#### BibLaTeX

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