Abstract
A partitioned, priority-queue algorithm for solving the single-source best-path problem is defined and evaluated. Finding single-source paths for sparse graphs is notable because of its definitelack of parallelism-no known algorithms are scalable. Qualitatively, we discuss the close relationships between our algorithm and previous work by Quinn, Chikayama, and others. Performance measurements of variations of the algorithm, implemented both in concurrent and imperative programming languages on a shared-memory multiprocessor, are presented. This quantitative analysis of the algorithms provides insights into the tradeoffs between complexity and overhead in graph-searching executed in high-level parallel languages with automatic task scheduling.
Similar content being viewed by others
References
K. L. Clark and S. Gregory, PARLOG: Parallel Programming in Logic, (ed.), E. Y. Shapiro,Concurrent Prolog: Collected Papers, MIT Press, Cambridge, Massachusetts1:84–139 (1987).
M. Quinn and Y. Yoo, Data Structures for the Efficient Solution of Graph Theoretic Problems on Tightly Coupled MIMD Computers,Int'l. Conf. on Parallel Processing, Penn State, pp. 431–438 (August 1984).
E. F. Moore, The Shortest Path Through a Maze,Proc. of the Int'l. Symp. on Theory of Switching, Harvard University Press, Cambridge, Massachusetts, pp. 285–292 (April 1957).
K. Wada and H. Ichiyoshi, A Study of Mapping Locally Message Exchanging Algorithms on a Loosely-Coupled Multiprocessor, Technical Report 587, ICOT, 1-4-28 Mita, Minato-ku Tokyo 108, Japan (August 1990).
E. Y. Shapiro, The Family of Concurrent Logic Programming Languages,ACM Computing Surveys 21(3):413–510 (September 1989).
E. W. Dijkstra, A Note on Two Problems in Connexion with Graphs,Numerical Mathematics 1:269–271 (1959).
E. Tick, Parallel Logic Programming Algorithms for the Bestpath Problem, Technical Report TRIE-89-4, University of Tokyo (1989).
D. B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks,Journal of the ACM 24:1–13 (1977).
R. E. Tarjan,Data Structures and Network Algorithms, Regional Conference Series in Applied Mathematics. Volume 44, Society for Industrial and Applied Mathematics, Philadelphia Pennsylvania, (1983).
N. Deo, C. Pang, and R. Lord, Two Parallel Algorithms for the Shortest Path Problems,Int'l. Conf. on Parallel Processing, Penn State, pp. 244–253 (August 1980).
V. N. Rao and V. Kumar, Concurrent Insertions and Deletions in a Priority Queue,Int'l. Conf. on Parallel Processing, Penn State, (August 1988).
V. Kumar and V. Singh, Scalability of Parallel Algorithms for the All Pairs Shortest Path Problem: A Summary of Results,Int'l Conf. on Parallel Processing, Penn State,3:136–140 (August 1990).
R. Paige and C. Kruskal, Parallel Algorithms for Shortest Path Problems,Int'l Conf. on Parallel Processing, Penn State, pp. 14–19 (August 1985).
U. Pape, Implementation and Efficiency of Moore-Algorithms for the Shortest Route Problems,Math. Programming 7:212–222 (1974).
E. Y. Shapiro and C. Mierowsky, Fair, Biased, and Self-Balancing Merge Operators: Their Specification and Implementation in Concurrent Prolog,Int'l. Symp. on Logic Programming, Atlantic City, IEEE Computer Society, Silver Spring, Maryland, pp. 83–92.
M. Sato and A. Goto, Evaluation of the KL1 Parallel System on a Shared Memory Multiprocessor.IFIP Working Conf. on Parallel Processing, Pisa, North Holland, pp. 305–318 (May 1988).
T. Chikayama, Personal Communication, ICOT, Tokyo (1989).
E. Tick and P. Adamson, Partitioned Graph-Search Algorithms, Technical Report CIS-TR-91-01a, University of Oregon, Department of Computer Science (July 1992).
J. A. Crammond, A. Davison, A. Burt, M. Huntbach, and M. Lam, The Parallel Parlog User Manual, Technical Report, Department of Computing, Imperial College (June 1990).
J. A. Crammond, Scheduling and Variable Assignment in the Parallel Parlog Implementation,North American Conference on Logic Programming, Austin, MIT Press, pp. 642–657 (October 1990).
Author information
Authors and Affiliations
Additional information
Presently at Intel-PCED.
Rights and permissions
About this article
Cite this article
Adamson, P., Tick, E. Greedy partitioned algorithms for the shortest-path problem. Int J Parallel Prog 20, 271–298 (1991). https://doi.org/10.1007/BF01408019
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01408019