Abstract
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.