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

Source abstract

Consider the minimal weights of paths between two points in a complete graph K n 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.