A partitioned, priority-queue algorithm for solving the single-source best-path problem is defined and evaluated. Implemented in a concurrent parallel logic programming language, and measured on a shared-memory multiprocessor, the algorithm achieves high performance and scalability, significantly better than previous attempts at solving this problem. Qualitatively, we discuss the close relationships between the algorithm and previous work by Quinn, Chikayama, and others. A quantitative analysis of the algorithms provide insights into the tradeoffs between complexity and overhead in graph-searching executed in high-level parallel languages with automatic task scheduling.
This article was published in the International Journal of Parallel Programming, vol. 20, no. 4, August 1991. This version has been extended with Appendicies containing the source programs analyzed.