A parallel shortest path algorithm | Computing Skip to main content
Springer Nature Link
Log in

A parallel shortest path algorithm

Ein paralleler Algorithmus für das Problem des kürzesten Weges

  • Published:
Computing Aims and scope Submit manuscript

Abstract

A new algorithm to find the shortest path between a pair of nodes is presented. In one hand this algorithm expands the search from origin and destination simultaneously, on the other hand it uses a lower bound for the shortest path to guide this search. Computational comparisons with existing algorithms show its efficiency. The implementation on a parallel computer is also discussed.

Zusammenfassung

Wir entwickeln einen neuen Algorithmus, um den kürzesten Weg zwischen einem Paar Knoten zu finden. Einerseits sucht er gleichzeitig ab Start und Ziel und andererseits benutzt er eine untere Grenze der kürzesten Wege, um die Suche zu führen. Vergleiche mit andere Algorithmen zeigen seine Leistung. Wir beschreiben auch die Implementierung auf einen parallelen Computer.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Boothroyd, J.: Algorithm 22: shortest path between start node and end of a network. Computer J.10, 306–307 (1967).

    Article  Google Scholar 

  2. Bovet, J.: Une amélioration de la méthode de Dijkstra pour la recherche d'un plus court dans un réseau. Discrete Applied Math.13, 93–96 (1986).

    Article  Google Scholar 

  3. Deo, N., Pang, C.: Shortest-path algorithms: taxonomy and annotation. Networks14, 275–323 (1984).

    Google Scholar 

  4. Dial, R. B.: Algorithm 360: shortest path forest with topological ordering. Comm. of the A.C.M.12, 632–633 (1969).

    Google Scholar 

  5. Dijkstra, E. W.: A note on two problems in connection with graphs. Numerische Mathematik1, 269–271 (1959).

    Article  Google Scholar 

  6. Dreyfus, S. E.: An appraisal of some shortest-path algorithms. Oper. Res.17, 395–412 (1969).

    Google Scholar 

  7. Gallo, G., Pallottino, S.: Shortest path methods: a unifying approach. Math. Prog.26, 38–64 (1986).

    Google Scholar 

  8. Gallo, G., Pallottino, S., Ruggeri, C., Storchi, G.: A bibliography on shortest paths. CNR. PF Informatica SOFMAT rapp 27.82 (1982).

  9. Nicholson, T. A.: Finding the shortest route between two points in a network. Computer J.9, 275–280 (1966).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department de Mathématiques, EPFL-Ecublens, CH-1015, Lausanne, Switzerland

    Th. Mohr & C. Pasche

Authors
  1. Th. Mohr
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. Pasche
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mohr, T., Pasche, C. A parallel shortest path algorithm. Computing 40, 281–292 (1988). https://doi.org/10.1007/BF02276912

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

AMS Subject Classifications

Key words

Search

Navigation