In this talk we propose a natural straight-forward implementation of Dijkstra's shortest path algorithm for directed weighted graphs represented as a weight matrix on a model of associative parallel processors of the SIMD type with bit-serial (or vertical) processing (the STAR-machine). We show that the use of such an architecture allows us to obtain a simple and natural parallelization of all parts of Dijkstra's algorithm. We also show how to extend this implementation in a natural and robust way for restoring the shortest path from the source vertex to any given vertex. These algorithms are represented as the corresponding STAR procedures whose correctness is proved. We have also shown that every of these procedures takes O(rn) time, where r is the number of bits required for coding the maximal weight of shortest paths from the source vertex.
Keywords: multimedia, human-computer interfaces, computer software, information systems, communication via films.
IEEE Task Force on Cluster Computing