Abstract-A family of distributed algorithms for the dynamic
computation of the shortest paths in a computer network or
Memet is presented, validated, and analyzed. According to these
algorithms, each node maintains a vector with its distance to
every other node. Update messages from a node are sent only
to its neighbors; each such message contains a dktance vector
of one or more entries, and each entry specifies the length
of the selected path to a network destination, as well as m
indication of whether the entry constitutes an update, a query,
or a reply to a previous query. The new algorithms treat the
problem of distributed shortest-path routing as one of diffusing
computations, which was firzt proposed by Dijkztra and Scholten.
They improve on algorithms introduced previously by Chandy
and Misra, JatYe and Moss, Merlin and Segatl, and the author.
The new algorithms are shown to converge in finite time after
an arbitrary sequence of link coat or topological changes, to be
loop-free at every instan~ and to outperform all other loop-free
routing algorithms previously proposed from the standpoint of
the combined temporal, message, and storage complexities.
