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

Research output: Contribution to journalConference article

Abstract

We describe an O(n3/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 (1976), Takaoka (1992), Dobosiewicz (1990), Han (2004), Takaoka (2004), and Zwick (2004). The new algorithm is surprisingly simple and different from previous ones.

Original languageEnglish (US)
Pages (from-to)318-324
Number of pages7
JournalLecture Notes in Computer Science
Volume3608
DOIs
StatePublished - 2005
Externally publishedYes
Event9th International Workshop on Algorithms and Data Structures, WADS 2005 - Waterloo, Canada
Duration: Aug 15 2005Aug 17 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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