• DocumentCode
    887211
  • Title

    All paths through a maze

  • Author

    Kroft, D.

  • Author_Institution
    Columbia University, New York, N. Y.
  • Volume
    55
  • Issue
    1
  • fYear
    1967
  • Firstpage
    88
  • Lastpage
    90
  • Abstract
    The author considers a specific maze shown as a figure. The question is to enumerate all 46 paths between two specificn points. It is supposed that if one tries manually, that he will probably find about three-fourths of all the paths and then become bogged down with redundancy. In the remainder of this letter, the author not only shows how to enumerate all paths from some starting nodet to some end node in a straightforward one-pass technique, but also how to determine the total number of paths between any two specific nodes. The second piece of information is determined essentially for no additional cost. The matrix technique of Murchland (1965) for generating all paths in maze or graph requires the eliminaotion of paths produced which contain a loop. Consequently, the author believes that the method proposed here is more efficient. Also, this new technique has a simpliclty, as found in Moore??s Shortest Route Algorithm (1957), which is not found in Murchland??s.
  • Keywords
    Counting circuits; Flowcharts; Logic; Machinery; Network theory (graphs);
  • fLanguage
    English
  • Journal_Title
    Proceedings of the IEEE
  • Publisher
    ieee
  • ISSN
    0018-9219
  • Type

    jour

  • DOI
    10.1109/PROC.1967.5389
  • Filename
    1447319