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 ½N³ additions, ½N³ comparisons, and ½N³ transmissions of simple messages 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.Foundation Research Program of the Naval Postgraduate SchoolChief of Naval ResearchApproved for public release; distribution is unlimited