All paths through a maze
- 1 January 1967
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE
- Vol. 55 (1) , 88-90
- https://doi.org/10.1109/proc.1967.5389
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
This publication has 2 references indexed in Scilit:
- Bulk Processing in Distributed Logic MemoryIEEE Transactions on Electronic Computers, 1965
- SNOBOL , A String Manipulation LanguageJournal of the ACM, 1964