Successive shortest paths in complete graphs with random edge weights. Issue 4 (13th October 2020)

• Record Type: Journal Article
• Authors: Gerke, Stefanie; Mezei, Balázs F.; Sorkin, Gregory B.
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 1205
• Page End: 1247
• Publication Date: 2020-10-13
• Subjects: Dijkstra's algorithm -- minimum‐cost flow -- optimization in random structures -- robust optimization -- second‐cheapest structure -- shortest path; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20962
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .