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:
  • EdgeWeightAutomaticweight for each edge
    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:

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