Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model

We study the average-case complexity of shortest-paths problems in the vertex-potential model. The vertex-potential model is a family of probability distributions on complete directed graphs with \emph{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^2)$ expected time, and the all-pairs shortest-paths problem can be solved in $O(n^2 \log n)$ expected time