A Caltech Library Service

Distributed computation on graphs: shortest path algorithms

Chandy, K. M. and Misra, J. (1982) Distributed computation on graphs: shortest path algorithms. Communications of the ACM, 25 (11). pp. 833-837. ISSN 0001-0782. doi:10.1145/358690.358717.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
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.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)81-0205
Subject Keywords:distributed computation, shortest path, negative cycle, depth first search, diffusing computation
Issue or Number:11
Record Number:CaltechAUTHORS:20190111-085547749
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92211
Deposited By: Tony Diaz
Deposited On:11 Jan 2019 17:48
Last Modified:16 Nov 2021 03:48

Repository Staff Only: item control page