An empirical study of the structure of the shortest path tree
Mindaugas Bloznelis
Vilnius University
Irmantas Radavičius
Vilnius University
Published 2008-12-21


shortest path tree
weighted graph
random weights

How to Cite

Bloznelis M. and Radavičius I. (2008) “An empirical study of the structure of the shortest path tree”, Lietuvos matematikos rinkinys, 48(proc. LMS), pp. 338–342. doi: 10.15388/LMR.2008.18118.


We consider a complete graph on n vertices. Edges of the graph are prescribed random positive weights X1, X2, . . ., Xm. 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 T1, T2, . . . ⊂ T denote the trees that are obtained from T after removal of  the root v. Let N1 \geq N2 \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.

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Please read the Copyright Notice in Journal Policy