A Decentralized Algorithm for Finding the Shortest Paths in Defense Communications Networks

摘要

This paper presents a decentralized shortest path algorithm which finds the shortest distances between all pairs of nodes without requiring that any particular node have information about the complete topology of the network. The algorithm requires at most N3/2 additions, N3/2 comparisons, and N3/2 transmissions of simple message between individual nodes. The computational upper bound of the present algorithm is lower than that of Dijkstra's centralized shortest path algorithm and is 1/N of the upper bound of Abram and Rhodes' decentralized shortest path algorithm. (Author)