 GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/Distance

GraphTheory

 Distance
 distance between two vertices

 Calling Sequence Distance(G, s, t)

Parameters

 G - graph s, t - vertices of the graph

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).
 • For weighted graphs, the weights of edges are ignored. Use the AllPairsDistance, DijkstrasAlgorithm, or BellmanFordAlgorithm commands to compute weighted distances between vertices.
 • 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 unweighted 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{DP}≔\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{DP}}{≔}{\mathrm{Graph 2: a directed unweighted graph with 10 vertices and 15 arc\left(s\right)}}$ (4)
 > $\mathrm{Distance}\left(\mathrm{DP},1,4\right)$
 ${3}$ (5)
 > $\mathrm{ShortestPath}\left(\mathrm{DP},1,4\right)$
 $\left[{1}{,}{2}{,}{3}{,}{4}\right]$ (6)