Average-case complexity of shortest-paths problems in the vertex-potential model

We study the average-case complexity of shortest-paths problems in the vertexpotential model. The vertex-potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and with respect to this model, the single-source shortest-paths problem can be solved in O(n²) expected time, and the all-pairs shortest-paths problem ca