ignoreweights=truefalse

Specifies whether to ignore edge weights if present.

ShortestPath(G, u, v) returns a shortest path from u to v in G using a breadth-first search. The output is a list of vertices in the order they appear on the path. If no such a path exists, an error message is displayed.

If G is undirected, the output is a shortest path between u and v. If G is directed, the output is a shortest directed path from u to v.

If G has weighted edges then the output is a shortest weighted path between u and v computed using either DijkstrasAlgorithm or BellmanFordAlgorithm depending on whether there are negative edge weights.  To ignore the edge weights and compute the path with the fewest edges, use the option ignoreweights.

If v is not reachable from u, the empty path $\left[\right]$ will be returned.

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

$\mathrm{C6}≔\mathrm{CycleGraph}\left(6\right)$

$\mathrm{C6}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 6\; edge(s)}$

$\mathrm{IsReachable}\left(\mathrm{C6}\,1\,5\right)$

$\mathrm{true}$

$\mathrm{ShortestPath}\left(\mathrm{C6}\,1\,5\right)$

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

$\mathrm{W6}≔\mathrm{Graph}\left(\left\{\left[\left[1\,2\right]\,10\right]\,\left[\left[1\,6\right]\,6\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]\,5\right]\right\}\right)$

$\mathrm{W6}≔\mathrm{Graph\; 2:\; a\; directed\; weighted\; graph\; with\; 6\; vertices\; and\; 6\; arc(s)}$

$\mathrm{DrawGraph}\left(\mathrm{W6}\,'\mathrm{layout}'='\mathrm{circle}'\right)$

$\mathrm{ShortestPath}\left(\mathrm{W6}\,1\,6\right)$

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

$\mathrm{ShortestPath}\left(\mathrm{W6}\,6\,1\right)$

$\mathrm{ShortestPath}\left(\mathrm{W6}\,1\,6\,'\mathrm{ignoreweights}'\right)$

$\left[1\,6\right]$

The GraphTheory[ShortestPath] command was updated in Maple 2024.

The ignoreweights option was introduced in Maple 2024.

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