Online Help

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](...).

$\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)$

$\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)$