{
  "id": "1105.3770",
  "version": "v1",
  "published": "2011-05-19T00:42:48.000Z",
  "updated": "2011-05-19T00:42:48.000Z",
  "title": "All-Pairs Shortest Paths in $O(n^2)$ time with high probability",
  "authors": [
    "Yuval Peres",
    "Dimitry Sotnikov",
    "Benny Sudakov",
    "Uri Zwick"
  ],
  "categories": [
    "math.CO",
    "cs.DS",
    "math.PR"
  ],
  "abstract": "We present an all-pairs shortest path algorithm whose running time on a complete directed graph on $n$ vertices whose edge weights are chosen independently and uniformly at random from $[0,1]$ is $O(n^2)$, in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of \\emph{locally shortest paths} in such randomly weighted graphs is $O(n^2)$, in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in $O(\\log^{2}n)$ expected time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-05-19T00:42:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "high probability",
      "dynamic all-pairs shortest paths algorithm",
      "all-pairs shortest path algorithm",
      "long standing open problem",
      "random edge update"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1105.3770P"
    }
  }
}