An empirical study of the structure of the shortest path tree (Q2811605)

Edges of a complete graph on \(n\) vertices are prescribed random positive weights \(X_1, X_2, \dots , X_{{n \choose 2}}\). These random variables are assumed to be independent and have the common probability distribution with density function \(f(x)\), \(x \geq 0\). Let \(T\) denote the shortest path tree with root \(v\) for a given vertex \(v\). Let \(T_1, T_2, \dots\) denote the subtrees obtained from \(T\) by removing the root \(v\). Let the sizes of these subtrees be arranged as the sequence \(N_1 \geq N_2 \geq N_3 \geq \cdots\). This paper reports simulations of statistical properties of this sequence for some specific functions \(f\) and large \(n\).