Published November 1982
| public
Journal Article
Distributed computation on graphs: shortest path algorithms
- Creators
- Chandy, K. M.
- Misra, J.
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
- Eprint ID
- 92211
- DOI
- 10.1145/358690.358717
- Resolver ID
- CaltechAUTHORS:20190111-085547749
- 81-0205
- Air Force Office of Scientific Research (AFOSR)
- Created
-
2019-01-11Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field