Abstract

This paper proposes a technique to build the data structure for finding the second simple shortest paths on a model of associative parallel processors (the STAR-machine). It includes three associative parallel algorithms represented on the STAR-machine as the corresponding procedures. We prove the correctness of these procedures and evaluate their time complexity. Among these algorithms, the new version of the Dijkstra algorithm and the associative parallel algorithm for finding the matrix of tree paths can be used to solve other graph problems on the STAR-machine.

File

nepomn.pdf156.5 KB

Pages

43-57