THE SHORTEST-PATH PROBLEM FOR GRAPHS WITH RANDOM ARC-LENGTHS

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 is considered. An algorithm is described which solves this problem in O(n(m plus n log n) expected time, where m is the expected number of arcs with finite length. The authors consider also the case when the arc-lengths are random variables which are independently distributed with distribution function F, where F(O) equals 0 and F is differentiable at 0; for this case, they describe an algorithm which runs in O(n**2 log n) expected time.