An empirical study of the structure of the shortest path tree

Abstract

We consider a complete graph on n vertices. Edges of the graph are prescribed random positive weights X₁, X₂, . . ., X_m. Here m = (n/2). We assume that these random variables are independent and have the common probability distribution with density function f (x), x \geq 0. Given a vertex v let T denote the shortest path tree with root v. Let T₁, T₂, . . . ⊂ T denote the trees that are obtained from T after removal of  the root v. Let N₁ \geq N₂ \geq  N₃  \geq . . . denote (ordered) sequence of sizes of these trees. We study statistical properties of this sequence for various densities f and large n.