Skip to main content
SpringerLink
Log in

Greedy partitioned algorithms for the shortest-path problem

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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).

    Google Scholar 

  2. 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).

  3. 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).

    Google Scholar 

  4. 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).

  5. E. Y. Shapiro, The Family of Concurrent Logic Programming Languages,ACM Computing Surveys 21(3):413–510 (September 1989).

    Google Scholar 

  6. E. W. Dijkstra, A Note on Two Problems in Connexion with Graphs,Numerical Mathematics 1:269–271 (1959).

    Google Scholar 

  7. E. Tick, Parallel Logic Programming Algorithms for the Bestpath Problem, Technical Report TRIE-89-4, University of Tokyo (1989).

  8. D. B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks,Journal of the ACM 24:1–13 (1977).

    Google Scholar 

  9. 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).

    Google Scholar 

  10. 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).

  11. V. N. Rao and V. Kumar, Concurrent Insertions and Deletions in a Priority Queue,Int'l. Conf. on Parallel Processing, Penn State, (August 1988).

  12. 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).

    Google Scholar 

  13. R. Paige and C. Kruskal, Parallel Algorithms for Shortest Path Problems,Int'l Conf. on Parallel Processing, Penn State, pp. 14–19 (August 1985).

  14. U. Pape, Implementation and Efficiency of Moore-Algorithms for the Shortest Route Problems,Math. Programming 7:212–222 (1974).

    Google Scholar 

  15. 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.

  16. 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).

    Google Scholar 

  17. T. Chikayama, Personal Communication, ICOT, Tokyo (1989).

  18. E. Tick and P. Adamson, Partitioned Graph-Search Algorithms, Technical Report CIS-TR-91-01a, University of Oregon, Department of Computer Science (July 1992).

  19. 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).

  20. 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).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Oregon, Oregon, USA

    E. Tick

Authors
  1. P. Adamson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E. Tick
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Presently at Intel-PCED.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01408019

Key Words

Search

Navigation