Combinatorics, Probability and Computing

One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights

a1 Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden (e-mail:


Consider the minimal weights of paths between two points in a complete graph Kn with random weights on the edges, the weights being, for instance, uniformly distributed. It is shown that, asymptotically, this is log n/n for two given points, that the maximum if one point is fixed and the other varies is 2 log n/n, and that the maximum over all pairs of points is 3 log n/n.

Some further related results are given as well, including results on asymptotic distributions and moments, and on the number of edges in the minimal weight paths.

(Received December 12 1997)
(Revised October 19 1998)