Abstract

In this paper, by means of a model of associative parallel systems with the vertical processing (the STAR-machine), we propose a natural straight forward representation of the Edmonds–Karp version of performing the Ford shortest path algorithm. We present the associative parallel algorithm as the corresponding STAR procedure and prove its correctness. Moreover, we provide special tools for maintaining graphs with the negative arc weights on associative parallel processors.

File
nepomn.pdf197.12 KB
Issue
Pages
29-42