Successive shortest paths in complete graphs with random edge weights. Issue 4 (13th October 2020) - Gerke, Stefanie; Mezei, Balázs F.; Sorkin, Gregory B.
Abstract : 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 2 k / n + ln n / n uniformly for all k  ≤  n  − 1. We show analogous results when the edge weights are drawn from an exponential distribution. The same results characterize the collectively cheapest k edge‐disjoint paths, that is, a minimum‐cost k ‐flow. We also obtain the expectation of X k conditioned on the existence of P k .