A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees.

摘要

This paper examines different algorithms for calculating the shortest path from one node to all other nodes in a network. More sepcifically, the authors seek to advance the state-of-the-art of computer implementation technology for such algorithms and the problems they solve by examining the effect of innovative computer science list structures and labeling techniques on algorithmic performance. The study shows that the procedures examined indeed exert a powerful influence on solution efficiency, with identity of the best dependent upon the topology of the network and the range of the arc distance coefficients. The study further disclose that the shortest path algorithm previously documented as the most efficient is dominated for all problems structures by the new methods, which are sometimes an order of magnitude faster. (Author)