GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

Distance

 

Calling Sequence

Parameters

Description

Examples

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

withGraphTheory:

withSpecialGraphs:

PPetersenGraph

PGraph 1: an undirected unweighted graph with 10 vertices and 15 edge(s)

(1)

DistanceP,1,4

2

(2)

ShortestPathP,1,4

1,5,4

(3)

DPGraphmapx→sortconvertx,list,EdgesP

DPGraph 2: a directed unweighted graph with 10 vertices and 15 arc(s)

(4)

DistanceDP,1,4

3

(5)

ShortestPathDP,1,4

1,2,3,4

(6)

See Also

AllPairsDistance

BellmanFordAlgorithm

Diameter

DijkstrasAlgorithm

ShortestPath