Abstract

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.

File
nep.pdf202.51 KB
Issue
Pages
61-71