Shortest path algorithms: A computational study with the C programming language

Shortest path algorithms: A computational study with the C programming language

0.00 Avg rating0 Votes
Article ID: iaor19921046
Country: United Kingdom
Volume: 18
Start Page Number: 767
End Page Number: 786
Publication Date: Nov 1991
Journal: Computers and Operations Research
Authors: , ,
Keywords: graphs, networks: path
Abstract:

The main purpose of this study is to evaluate the computational efficiency of algorithms for calculating shortest paths when they are correctly coded by using the C programming language. The eight algorithms that were selected for this experiment are the most efficient, either measured in terms of worst-case bounds or marked as such from previous computational studies; they include the redistributive heap algorithm. The authors suggest computer implementations that use the full power of C. In particular, the network representation and the various data structures used to keep the scan eligible list may be managed by using only additions and no multiplications, while it is not possible with FORTRAN. These capabilities, unique to C, yield several interesting conclusions: one may expect to speed up a shortest path algorithm by a factor of 20%; in some cases, this factor may reach 30%. Interestingly, the level of programming difficulty required to achieve these benefits is not greater than that required by implementations using arrays.

Reviews

Required fields are marked *. Your email address will not be published.