Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs1


Journal Article

We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O(f(n)/p + I(n) log n) on the PRAM using p processors, where I(n) is log n on the EREW PRAM, log log n on the CCRW PRAM, f(n) is o(n3). On the randomized CRCW PRAM we are able to achieve time complexity O(n3/p + log n) using p processors.

Full Text

Duke Authors

Cited Authors

  • Han, Y; Pan, VY; Reif, JH

Published Date

  • January 1, 1997

Published In

Volume / Issue

  • 17 / 4

Start / End Page

  • 399 - 415

International Standard Serial Number (ISSN)

  • 0178-4617

Digital Object Identifier (DOI)

  • 10.1007/BF02523680

Citation Source

  • Scopus