Finding single-source shortest paths using associative parallel processors

In this paper, we employ Dijkstra's algorithm for finding single-source shortest paths in directed graphs. We propose an efficient implementation of this algorithm on a model of associative parallel processors of the SIMD type with bit-serial (or vertical) processing (the STAR-machine). Moreover, we show how to extend this implementation for restoring the shortest path from the source vertex to a given vertex. These algorithms are represented as the corresponding STAR procedures whose correctness is verified and time complexity is evaluated. We also provide an experiment of finding the shortest path between two given vertices in a directed graph.