avoidvertices=list or set

Specifies vertices to avoid in building a path.

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

distance=truefalse

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

If true, each element of the list output of LongestPath 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.

endvertex=a valid vertex in G

Specifies a final vertex. If provided, the algorithm only considers paths terminating at endvertex.

ignoreweights=truefalse

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

startvertex=a valid vertex in G

Specifies the starting vertex. If provided, the algorithm only considers paths beginning at startvertex.

LongestPath(G) returns a path of maximum length in a directed acyclic graph G. The output is a list of vertices in the order they appear on the path.

If G is not a directed graph or has a directed cycle, an error is returned.

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

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

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

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

$\mathrm{LongestPath}\left(G\right)$

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

The GraphTheory[LongestPath] command was introduced in Maple 2025.

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