Shortest shortest path trees of a network (Q1917275): Difference between revisions

If \(N\) is an undirected network where each edge has positive length, we may consider the distances of vertices from a specified internal point of an edge. A shortest path tree (SPT) rooted at \(s\) (possibly an internal point of an edge) is a spanning tree \(T\) of the network \(N[s]\) (i.e., \(N\) with \(s\) as possibly a new vertex) where for each vertex \(v\) the length of the \(s\)-\(v\) path in \(T\) is equal to the \(s\)-\(v\) distance in \(N[s]\). We define \(d(x)\) to be the sum of the distances of \(x\) to all other vertices of \(N\); \(r(x)\) to be the number of edges of a shortest SPT (i.e., one with fewest edges) of \(N\) rooted at \(x\). Two algorithms are given: one to find a shortest SPT and another to find a maximum set of points \(x\) which are best relative to the sizes of \(d(x)\) and \(r(x)\). Both have complexity \(O(mn\log n)\).