Shortest-path tree

In graphs that have negative cycles, the set of shortest simple paths from v to all other vertices do not necessarily form a tree.

For simple connected graphs, shortest-path trees can be used[1] to suggest a non-linear relationship between two network centrality measures, closeness and degree.

From this one deduces that the inverse of closeness, a length scale associated with each vertex, varies approximately linearly with the logarithm of degree.

The relationship is not exact but it captures a correlation between closeness and degree in large number of networks constructed from real data[1] and this success suggests that shortest-path trees can be a useful approximation in network analysis.

Wide Area Network Design: Concepts and Tools for Optimization.

A simple example of a shortest-path tree.
Example of one of two shortest-path trees where the root vertex is the red square vertex. The edges in the tree are indicated with green lines while the two dashed lines are edges in the full graph but not in the tree. The numbers beside the vertices indicate the distance from the root vertex.