networks(deprecated)/shortpathtree - Maple Help

Home : Support : Online Help : networks(deprecated)/shortpathtree

networks

 shortpathtree
 construct a shortest path spanning tree

 Calling Sequence shortpathtree(G, v)

Parameters

 G - graph or network v - vertex

Description

 • Important: The networks package has been deprecated.Use the superseding command GraphTheory[DijkstrasAlgorithm] instead.
 • This is an implementation of Dijkstra's algorithm for shortest path spanning tree. A priority queue is used for storing the edges.
 • The final distances are recorded as the vertex weights in the resulting graph (a spanning tree). The tree is rooted at v and the ancestors and daughters of each node are computed relative to this tree.
 • Edge weights are assumed to be lengths or distances so that edge weights are required to be non-negative. Undirected edges are assumed to be bidirectional.
 • This routine is normally loaded via the command with(networks) but may also be referenced using the full name networks[shortpathtree](...).

Examples

Important: The networks package has been deprecated.Use the superseding command GraphTheory[DijkstrasAlgorithm] instead.

 > $\mathrm{with}\left(\mathrm{networks}\right):$
 > $G≔\mathrm{petersen}\left(\right):$
 > $T≔\mathrm{shortpathtree}\left(G,1\right):$
 > $\mathrm{ancestor}\left(T\right)$
 ${table}{}\left(\left[{2}{=}\left\{{1}\right\}{,}{3}{=}\left\{{2}\right\}{,}{4}{=}\left\{{5}\right\}{,}{5}{=}\left\{{1}\right\}{,}{6}{=}\left\{{1}\right\}{,}{7}{=}\left\{{6}\right\}{,}{9}{=}\left\{{5}\right\}{,}{8}{=}\left\{{2}\right\}{,}{10}{=}\left\{{6}\right\}\right]\right)$ (1)
 > $\mathrm{daughter}\left(T\right)$
 ${table}{}\left(\left[{1}{=}\left\{{2}{,}{5}{,}{6}\right\}{,}{2}{=}\left\{{3}{,}{8}\right\}{,}{3}{=}{\varnothing }{,}{4}{=}{\varnothing }{,}{5}{=}\left\{{4}{,}{9}\right\}{,}{6}{=}\left\{{7}{,}{10}\right\}{,}{7}{=}{\varnothing }{,}{9}{=}{\varnothing }{,}{8}{=}{\varnothing }{,}{10}{=}{\varnothing }\right]\right)$ (2)