skip to main content
article
Free Access

On finding minimum routes in a network with turn penalties

Published:01 February 1961Publication History
Skip Abstract Section

Abstract

In some highway engineering work it is necessary to find a route between two points in a city's street and freeway network such that a function of time and distance is minimized. Such a route is called a “best” route, and finding such a route is not a difficult task. The Moore Algorithm1 accomplishes this quite nicely, and using that algorithm and a procedure developed by Hoffman and Pavley2 (programmed by them for the IBM 650) it is even possible to find the “Nth best path.”

References

  1. 1 MOORE, E. F. The shortest path through a maze. In Proceedings of an International Symposium on the Theory of Switching, Part II, April 2-5, 1957, The Annals of the Computation Laboratory of Harvard University 30, Harvard University, 1959.Google ScholarGoogle Scholar
  2. 2 HOFFMAN, WALTER, AND PAVLEY, RICHARD. A method for the solution of the Nth best path problems. J. Assoc. Comp. Mach. 6 (1959), 506-514. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. On finding minimum routes in a network with turn penalties

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image Communications of the ACM
            Communications of the ACM  Volume 4, Issue 2
            Feb. 1961
            43 pages
            ISSN:0001-0782
            EISSN:1557-7317
            DOI:10.1145/366105
            • Editor:
            • Alan J. Perlis
            Issue’s Table of Contents

            Copyright © 1961 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 1 February 1961

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • article

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader