Properties of Labeling Methods for Determining Shortest Path Trees
- 1 May 1981
- journal article
- Published by National Institute of Standards and Technology (NIST) in Journal of Research of the National Bureau of Standards
- Vol. 86 (3) , 317-330
- https://doi.org/10.6028/jres.086.013
Abstract
A number of labeling procedures for determining shortest paths in a network employ a sequence list in order to carry out the required steps systematically. This paper studies certain formal properties of such sequence lists. It is shown that the desirable property of branching out from nodes whose labels represent actual in-tree distances is assured for certain ways of managing the sequence list, but not for others. The relationship of this property to the computational complexity of various labeling procedures is also investigated.Keywords
This publication has 0 references indexed in Scilit: