Concurrent selection of the shortest paths and distances in directed graphs using vertical processing systems

In this paper, we propose a new implementation of Dijkstra's shortest path algorithm on a model of associative parallel processors with the vertical data processing (the STAR-machine) to obtain for every vertex of a directed graph the distance along with the shortest path from the source vertex. We prove correctness of the corresponding procedure and evaluate its time complexity.