A simple implementation of Dijkstra's shortest path algorithm on associative parallel processors

• Autorzy: Nepomniaschaya A.S. , Dvoskina M.A.
• Języki publikacji: EN

Abstrakty

EN

In this paper we propose a natural straight forward implementation of Dijkstra's shortest path algorithm on a model of associative parallel processors of the SIMD type with bit-serial (or vertical) processing (the STAR-machine). In addition, we show how to extend this implementation for restoring the shortest path from the source vertex to a given vertex. These algorithms of implementation are represented as the corresponding STAR procedures whose correctness is verified and time complexity is evaluated.

Słowa kluczowe

EN

Dijkstra's shortest path algorithm; single-source shortest path problem; directed weighted graph; associative parallel processing; time complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2000
• Tom: Vol. 43, Nr 1-4
• Strony: 227--243
• Opis fizyczny: bibliogr. 20 poz.

Twórcy

autor

Nepomniaschaya A.S.

autor

Dvoskina M.A.

• Laboratory of Parallel Algorithms and Structures, Institute of Computational Mathematics and Mathematical Geophysics, Novosibirsk, Russia,