A Study of Point-to-Point Routing Problem in Mazes

Der-Cherng Liaw, Chien-Chih Kuo, Hung-Tse Lee

In this paper, a three-step design is proposed to solve the point-to-point problem in a given maze. First, a well-known “depth-first” algorithm is adopted to find all the possible connection among grids in the maze with a graph structure. The obtained graph will then be simplified by deleting both of non-intersection and non-end grids. Such a step will largely decrease the computation load for constructing the path between the starting grid and the desired destination in the given maze. Finally, based on simplified graph the Dijkstra’s algorithm is employed to find the shortest path between the starting grid and the destination. Numerical results of three typical examples are obtained to demonstrate the success of the proposed design.