T R A C K       P A P E R
ISSN:2394-3661 | Crossref DOI | SJIF: 5.138 | PIF: 3.854

International Journal of Engineering and Applied Sciences

(An ISO 9001:2008 Certified Online and Print Journal)

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

( Volume 6 Issue 7,July 2019 ) OPEN ACCESS
Author(s):

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

Abstract:

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.

Paper Statistics:

Total View : 390 | Downloads : 381 | Page No: 1-6 |

Cite this Article:
Click here to get all Styles of Citation using DOI of the article.