  Consider a complete graph $K_n$ with edge weights drawn independently from a
uniform distribution $U(0,1)$. The weight of the shortest (minimum-weight) path
$P_1$ between two given vertices is known to be $\ln n / n$, asymptotically.
Define a second-shortest path $P_2$ to be the shortest path edge-disjoint from
$P_1$, and consider more generally the shortest path $P_k$ edge-disjoint from
all earlier paths. We show that the cost $X_k$ of $P_k$ converges in
probability to $2k/n+\ln n/n$ uniformly for all $k \leq n-1$. We show analogous
results when the edge weights are drawn from an exponential distribution. The
same results characterise the collectively cheapest $k$ edge-disjoint paths,
i.e., a minimum-cost $k$-flow. We also obtain the expectation of $X_k$
conditioned on the existence of $P_k$.
