[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

An 0(n 2 lognloglogn) expected time algorithm for the all shortest distance problem

  • Communications
  • Conference paper
  • First Online:
Mathematical Foundations of Computer Science 1980 (MFCS 1980)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 88))

Abstract

In the present paper we improve Spira's algorithm for the all shortest distance problem and reduce the expected computing time from 0(n 2 log 2 n) to 0(n 2 lognloglogn) where n is the number of vertices in a graph. We also give an algorithm for distance matrix multiplication with 0(n 2 logn) comparisons and additions between distances where n is the dimension of matrices.

On leave from Ibaraki University, Hitachi, Japan

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. E.W. Dijkstra, “A note on two problems in connection with graphs,” Numer. Math. 1, pp 269–271, (1959).

    Google Scholar 

  2. P.M. Spira, “A new algorithm for finding all shortest paths in a graph of positive arcs in average time 0(n 2 log 2 n),” SIAM Journal, Computing 2, pp 28–32, (1973).

    Google Scholar 

  3. J.S. Carson and A.M. Law, “A note on Spira's algorithm for the all pairs shortest path problem,” SIAM Journal, Computing 6, pp 696–699, (1977).

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

P. Dembiński

Rights and permissions

Reprints and permissions

Copyright information

© 1980 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Takaoka, T., Moffat, A. (1980). An 0(n 2 lognloglogn) expected time algorithm for the all shortest distance problem. In: Dembiński, P. (eds) Mathematical Foundations of Computer Science 1980. MFCS 1980. Lecture Notes in Computer Science, vol 88. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0022539

Download citation

  • DOI: https://doi.org/10.1007/BFb0022539

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-10027-0

  • Online ISBN: 978-3-540-38194-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics