mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

and

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, a shortest-path tree rooted at a vertex ''v'' of a connected,

undirected In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

''G'' is a

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...

''T'' of ''G'', such that the path distance from root ''v'' to any other vertex ''u'' in ''T'' is the

shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two ...

distance from ''v'' to ''u'' in ''G''. In connected graphs where shortest paths are well-defined (i.e. where there are no negative-length cycles), we may construct a shortest-path tree using the following algorithm: # Compute dist(''u''), the shortest-path distance from root ''v'' to vertex ''u'' in ''G'' using

Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...

Bellman–Ford algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex (graph theory), vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more ...

. # For all non-root vertices ''u'', we can assign to ''u'' a parent vertex ''p_u'' such that ''p''_''u'' is connected to ''u'', and that dist(''p''_''u'') + edge_dist(''p''_''u'',''u'') = dist(''u''). In case multiple choices for ''p_u'' exist, choose ''p''_''u'' for which there exists a shortest path from ''v'' to ''p''_''u'' with as few edges as possible; this tie-breaking rule is needed to prevent loops when there exist zero-length cycles. # Construct the shortest-path tree using the edges between each node and its parent. The above algorithm guarantees the existence of shortest-path trees. Like

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. ...

s, shortest-path trees in general are not unique. In graphs for which all edge weights are equal, shortest path trees coincide with

breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next dept ...

trees. 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 to suggest a non-linear relationship between two network centrality measures, closeness and degree. By assuming that the branches of the shortest-path trees are statistically similar for any root node in one network, one may show that the size of the branches depend only on the number of branches connected to the root vertex, i.e. to the degree of the root node. 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 and this success suggests that shortest-path trees can be a useful approximation in network analysis.

References

Spanning tree {{Graph-stub

See also

References

References