Shortest Paths in Matrix Multiplication Time

Piotr SankowskiESA 2005 · OpenReview

Abstract

In this paper we present an \({\tilde O}(W n^{\omega})\) time algorithm solving single source shortest path problem in graphs with integer weights from the set {–W,...,0,...,W}, where ω < 2.376 is the matrix multiplication exponent. For dense graphs with small edge weights, this result improves upon the algorithm of Goldberg that works in \({\tilde O}(mn^{0.5}{\rm log}W)\) time, and the Bellman-Ford algorithm that works in O(nm) time.
BibTeX
@inproceedings{sankowski2005shortest,
  author = {Piotr Sankowski},
  title = {{Shortest Paths in Matrix Multiplication Time}},
  booktitle = {ESA},
  year = {2005},
  url = {https://openreview.net/forum?id=uy7qOhy5pt},
}

Loading related content...

Figure