ShortestPath - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

# Online Help

###### All Products    Maple    MapleSim

GraphTheory

 ShortestPath
 find a shortest path between two vertices

 Calling Sequence ShortestPath(G, u, v)

Parameters

 G - graph u, v - vertices of the graph

Options

 • ignoreweights=truefalse
 Specifies whether to ignore edge weights if present.

Description

 • 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.

Examples

 > $\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\left(s\right)}}$ (1)
 > $\mathrm{IsReachable}\left(\mathrm{C6},1,5\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{ShortestPath}\left(\mathrm{C6},1,5\right)$
 $\left[{1}{,}{6}{,}{5}\right]$ (3)
 > $\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\left(s\right)}}$ (4)
 > $\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]$ (5)
 > $\mathrm{ShortestPath}\left(\mathrm{W6},6,1\right)$
 $\left[\right]$ (6)
 > $\mathrm{ShortestPath}\left(\mathrm{W6},1,6,'\mathrm{ignoreweights}'\right)$
 $\left[{1}{,}{6}\right]$ (7)

Compatibility

 • 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.

 See Also