Online Help

avoidvertices=list or set

Specifies vertices to avoid in building a path.

If vertices are specified here, the resulting path may not be shortest in G.

distance=truefalse

Specifies whether to return the distance along with the shortest path.

If true, each element of the list output of ShortestPath will be a two-element list, the first element of which is the path and the second of which is the weighted path distance to the common ancestor.

ignoreweights=truefalse

Specifies whether to ignore edge weights if present. The default is false.

ShortestAncestralPath(G,u,v) returns a shortest ancestral path of u and v in the directed graph G.

ShortestAncestralPath(G,C) returns a shortest ancestral path of the vertices C in the directed graph G.

ShortestDescendantPath(G,u,v) returns a shortest descendant path of u and v in the directed graph G.

ShortestDescendantPath(G,C) returns a shortest descendant path of the vertices C in the directed graph G.

A vertex u is a common ancestor of a set C of vertices of G if it is an ancestor of each vertex in C.

If G is a directed graph and u and v are vertices of G, an ancestral path of u and v is a pair (p,q) where p is a directed path from w to u, and q is a directed path from w to v, where w is an ancestor of both u and v.

A shortest ancestral path of u and v is an ancestral path of minimum length over all common ancestors, where the length is defined as the sum of the lengths of the two directed paths from a common ancestor to u and to v respectively.

A descendant path and shortest descendant path is defined analogously for descendants.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{GraphTheory}:-\mathrm{Graph}\left(6\,\left\{\left[1\,2\right]\,\left[2\,3\right]\,\left[2\,5\right]\,\left[3\,4\right]\,\left[3\,6\right]\,\left[4\,5\right]\,\left[4\,6\right]\right\}\right)$

$G≔\mathrm{Graph\; 1:\; a\; directed\; graph\; with\; 6\; vertices\; and\; 7\; arcs}$

$\mathrm{DrawGraph}\left(G\,\mathrm{style}=\mathrm{tree}\right)$

$\mathrm{ShortestAncestralPath}\left(G\,5\,6\right)$

$\left[\left[4\,5\right]\,\left[4\,6\right]\right]$

$\mathrm{ShortestAncestralPath}\left(G\,5\,6\,\mathrm{avoidvertices}=\left\{4\right\}\right)$

$\left[\left[2\,5\right]\,\left[2\,3\,6\right]\right]$

The GraphTheory[ShortestAncestralPath] and GraphTheory[ShortestDescendantPath] commands were introduced in Maple 2025.

For more information on Maple 2025 changes, see Updates in Maple 2025 .