非表示:
キーワード:
-
要旨:
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 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.