The shortest-path problem for graphs with random arc-lengths (Q1086251)

We consider the problem of finding the shortest distance between all pairs of vertices in a complete digraph on n vertices, whose arc-lengths are non-negative random variables. We describe an algorithm which solves this problem in \(O(n(m+n \log n))\) expected time, where m is the expected number of arcs with finite length. If m is small enough, this represents a small improvement over the bound in \textit{P. A. Bloniarz} [Techn. Rep. 80-3, Dept. Comput. Sci., SUNY at Albany (August 1980); see also SIAM J. Comput. 12, 588-560 (1983; Zbl 0521.68078)]. We consider also the case when the arc-lengths are random variables which are independently distributed with distribution function F, where \(F(0)=0\) and F is differentiable at 0; for this case, we describe an algorithm which runs in \(O(n^ 2\log n)\) expected time. In our treatment of the shortest-path problem we consider the following problem in combinatorial probability theory. A town contains n people, one of whom knows a rumour. At the first stage he tells someone chosen randomly from the town; at each stage, each person who knows the rumour tell someone else, chosen randomly from the town and independently of all other choices. Let \(S_ n\) be the number of stages before the whole town knows the rumour. We show that \(S_ n/\log_ 2n\to 1+\log_ e2\) in probability as \(n\to \infty\), and estimate the probabilities of large deviations in \(S_ n\).