A performance comparison of labeling algorithms for calculating shortest path trees
Judith F Gilsinn · 1973
Many applications in transportation and communication require the calculation of shortest routes between points in a network, and several algorithms for the solution of this problem exist in the literature.This paper examines one class of such algorithms, that which calculates a short- est route from one point in the network to all other intersection points.Computer data handling techniques which can be used to improve the two basic algorithms in this class are investigated.Results of computer timing runs on various types and sizes of networks are compared, and the differences, sometimes of an order of magnitude, are analyzed.Detailed flowcharts and computer programs of the tested algorithms are also included.