Successive shortest paths in complete graphs with random edge weights

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

l n 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 + l n n / n

uniformly for all

k l e q 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}

.

Recommendations

Cites Work

Cited In (9)

This page was built for publication: Successive shortest paths in complete graphs with random edge weights