CaltechAUTHORS
Published November 1982 | Version public
Journal Article Metadata-only

Distributed computation on graphs: shortest path algorithms

Creators

  • 1. ROR icon The University of Texas at Austin

Abstract

We use the paradigm of diffusing computation, introduced by Dijkstra and Scholten, to solve a class of graph problems. We present a detailed solution to the problem of computing shortest paths from a single vertex to all other vertices, in the presence of negative cycles.

Additional Information

© 1982 ACM. Received 7/80; revised 9/81; accepted 3/82. This work was supported in part by the Air Force Office of Scientific Research under grant AFOSR 81-0205. We are indebted to E. W. Dijkstra for his comments on an earlier draft of this paper; his suggestions led to more concise proofs in Section 5. We are also grateful to unknown referees and M. D. McIlroy for their suggestions and corrections.

Additional details

Identifiers

Eprint ID
92211
DOI
10.1145/358690.358717
Resolver ID
CaltechAUTHORS:20190111-085547749

Related works

Describes
10.1145/358690.358717 (DOI)

Funding

Air Force Office of Scientific Research (AFOSR)
81-0205

Dates

Created
2019-01-11
Created from EPrint's datestamp field
Updated
2021-11-16
Created from EPrint's last_modified field