A Distributed Algorithm for Shortest Paths
- 1 September 1982
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-31 (9), 898-899
- https://doi.org/10.1109/tc.1982.1676107
Abstract
Assuming that there is one processor at each vertex and all of these processors are synchronized, we can have a distributed algorithm for finding all the shortest paths in time O( d · p2) where d is the maximum of the degrees of vertices and p is the number of vertices.Keywords
This publication has 4 references indexed in Scilit:
- On finding and updating shortest paths and spanning treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973
- An Appraisal of Some Shortest-Path AlgorithmsOperations Research, 1969
- Algorithm 97: Shortest pathCommunications of the ACM, 1962
- A note on two problems in connexion with graphsNumerische Mathematik, 1959