The Longest Minimum-Weight Path in a Complete Graph
Louigi Addario‐Berry, Nicolas Broutin, Gábor Lugosi · Combinatorics Probability Computing · 2009
We consider the minimum-weight path between any pair of nodes of the n -vertex complete graph in which the weights of the edges are i.i.d. exponentially distributed random variables. We show that the longest of these minimum-weight paths has about α* log n edges, where α* ≈ 3.5911 is the unique solution of the equation α log α − α = 1. This answers a question posed by Janson [8].