Distance - Maple Help

GraphTheory

 Distance
 distance between two vertices

 Calling Sequence Distance(G, s, t)

Parameters

 G - graph s, t - vertices of the graph

Options

 • ignoreweights=truefalse
 Specifies whether to ignore edge weights if present.

Description

 • Distance returns the number of edges in the shortest path from s to t. If no such path exists, the output is infinity. The strategy is to use a breadth-first search (BFS) if the graph is unweighted and otherwise to use the same strategy as ShortestParth.
 • To find a path from s to t with minimum distance use the ShortestPath command.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $P≔\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 1: an undirected graph with 10 vertices and 15 edge\left(s\right)}}$ (1)
 > $\mathrm{Distance}\left(P,1,4\right)$
 ${2}$ (2)
 > $\mathrm{ShortestPath}\left(P,1,4\right)$
 $\left[{1}{,}{5}{,}{4}\right]$ (3)
 > $\mathrm{DMP}≔\mathrm{Graph}\left(\mathrm{map}\left(x↦\mathrm{sort}\left(\mathrm{convert}\left(x,\mathrm{list}\right)\right),\mathrm{Edges}\left(P\right)\right)\right)$
 ${\mathrm{DMP}}{≔}{\mathrm{Graph 2: a directed graph with 10 vertices and 15 arc\left(s\right)}}$ (4)
 > $\mathrm{Distance}\left(\mathrm{DMP},1,4\right)$
 ${3}$ (5)
 > $\mathrm{ShortestPath}\left(\mathrm{DMP},1,4\right)$
 $\left[{1}{,}{2}{,}{3}{,}{4}\right]$ (6)
 > $\mathrm{W6}≔\mathrm{Graph}\left(\left\{\left[\left[1,2\right],10\right],\left[\left[1,6\right],10\right],\left[\left[2,3\right],-10\right],\left[\left[3,4\right],10\right],\left[\left[4,5\right],-10\right],\left[\left[5,6\right],9\right]\right\}\right)$
 ${\mathrm{W6}}{≔}{\mathrm{Graph 3: a directed weighted graph with 6 vertices and 6 arc\left(s\right)}}$ (7)
 > $\mathrm{Distance}\left(\mathrm{W6},1,6\right)$
 ${9}$ (8)
 > $\mathrm{Distance}\left(\mathrm{W6},1,6,'\mathrm{ignoreweights}'\right)$
 ${1}$ (9)

Compatibility

 • The GraphTheory[Distance] command was updated in Maple 2024.
 • The ignoreweights option was introduced in Maple 2024.