Distributed shortest path algorithms for computer networks
Yen, Jin Y.
MetadataShow full item record
This paper presents two distributed algorithms for finding shortest paths from a source node to all other nodes in an N-node network. These algorithms are executed at individual nodes using only local information. Algorithm 1 works in networks where there are no topological changes such as link failures, link recoveries or changes of link lengths. Algorithm 2 is a mofification of Algorithm 1 for networks where there are topological changes. Algorithm 1 determines the optimal shortest paths in at most N3/4 steps, which is only one-half of the computational upper bounds of Abram and Rhodes' and Segall, Merlin and Gallager's algorithms. After the last topological change, Algorithm 2 determines the optimal shortest paths in the same number of steps as Algorithm 1. There are many situations where the present algorithms will work up to N/2 times faster than the algorithms proposed by these authors
NPS Report NumberNPS55-79-017
Showing items related by title, author, creator and subject.
Taylor, James G.; Neta, Beny (Monterey, California. Naval Postgraduate School, 2001-09); NPS-MA-01-001The goal of this study effort was to assess the ability of the Joint Conflict and Tactical Simulation (JCATS) to simulate the capabilities of non- lethal weapons (NLW) and to provide a product that can be incorporated into ...
De Kooter, Peter M. (Monterey, California. Naval Postgraduate School, 1997-03);As part of the existing acoustic transient localization program, a feasibility study was performed to apply existing algorithms to signals at higher carrier frequencies. The coherent matching, autocorrelation matching and ...
Armstrong, Robert Kyle (Monterey, California. Naval Postgraduate School, 1997-09);This thesis investigates, using in-line simulation, the effect of non-deterministic runtime distributions on the performance of SmartNet's schedule execution using the Opportunistic Load Balancing (OLB) Algorithm, the ...