Premium
A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
Author(s) -
Dial R.,
Glover F.,
Karney D.,
Klingman D.
Publication year - 1979
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230090304
Subject(s) - shortest path problem , computer science , node (physics) , average path length , algorithm , path (computing) , network topology , range (aeronautics) , theoretical computer science , mathematical optimization , mathematics , graph , computer network , materials science , structural engineering , engineering , composite material
This paper examines different algorithms for calculating the shortest path from one node to all other nodes in a network. More specifically, we seek to advance the state‐of‐the‐art of computer implementation technology for such algorithms and the problems they solve by exmining 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 the identity of the best dependent upon the topology of the network and the range of the arc distance coefficients. The study further discloses, for the problems tested, that the lable‐setting shortest path algorithm previously documented as the most efficient is dominated for all problem structures examined by the new methods.