Successive shortest paths in complete graphs with random edge weights
Successive shortest paths in complete graphs with random edge weights
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 , asymptotically. Define a second‐shortest path P 2 to be the shortest path edge‐disjoint from …