# 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:
•  EdgeWeight Automatic weight for each edge 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:

Introduced in 2010
(8.0)
|
Updated in 2015
(10.3)