All-pairs shortest paths with real weights in O(n 3/log∈n) time

Research output: Contribution to journalArticlepeer-review

Abstract

We describe an O(n 3/log∈n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (SIAM J. Comput. 5:49-60, 1976), Takaoka (Inform. Process. Lett. 43:195-199, 1992), Dobosiewicz (Int. J. Comput. Math. 32:49-60, 1990), Han (Inform. Process. Lett. 91:245-250, 2004), Takaoka (Proc. 10th Int. Conf. Comput. Comb., Lect. Notes Comput. Sci., vol. 3106, pp. 278-289, Springer, 2004), and Zwick (Proc. 15th Int. Sympos. Algorithms and Computation, Lect. Notes Comput. Sci., vol. 3341, pp. 921-932, Springer, 2004). The new algorithm is surprisingly simple and different from previous ones.

Original languageEnglish (US)
Pages (from-to)236-243
Number of pages8
JournalAlgorithmica (New York)
Volume50
Issue number2
DOIs
StatePublished - Feb 2008
Externally publishedYes

Keywords

  • Graph algorithms
  • Shortest paths

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'All-pairs shortest paths with real weights in O(n <sup>3</sup>/log∈n) time'. Together they form a unique fingerprint.

Cite this