TY - JOUR
TI - A Linear-C implementation of Dijkstra's algorithm
DO - https://doi.org/doi:10.7282/t3-g4x0-zp04
AU - Hsu, Chung-Hsing
AU - Smith, Don
AU - Levy, Saul
PY - 1996-10
AB - Linear-C is a data-parallel extension to C. In this report we show, by implementing Dijkstra's algorithm in Linear-C to solve the shortest-paths problem, that (1) data-parallelism in Dijkstra's algorithm can be easily expressed in Linear-C, (2) even a small amount of data parallelism can speed up the whole algorithm substantially, and (3) the algorithm, the data representation, and the efficiency are closely inter-related. Three implementations are provided, each with a different level of data parallelism exploited. The programs are explained, their time complexities are analyzed, and their strength and weakness in efficiency are compared.
LA - English
ER -