CNS using restricted space algorithms for finding a shortest path

  IJETT-book-cover  International Journal of Engineering Trends and Technology (IJETT)          
© 2011 by IJETT Journal
Volume-2 Issue-1                          
Year of Publication : 2011
Authors :Megha Gupta, Mohit Dua , Narendra Kumar


Megha Gupta, Mohit Dua , Narendra Kumar. "CNS using restricted space algorithms for finding a shortest path". International Journal of Engineering Trends and Technology (IJETT),V2(1):49-54 Jul to Aug 2011. ISSN:2231-5381. Published by Seventh Sense Research Group.


These days, due to the heavy traffic, it is very difficult for drivers in big cities to find an easy and efficient route to a selected destination. Thus, route guidance has become a very important problem for drivers. As a result, car navigation systems are commonly installed in new vehicles. These systems are capable of performing some of the tasks traditionally performed by driver, such as reading the map and determining the best route to the destination. The process of fi nding optimum path from one point to another is called routing. The suggested algorithm is improved version of dijkstra algorithm that can search for the shortest path at a restricted search space. The search space is restricted by the use of a rectangle or a static and dynamic hexagon. These methods can improve run time and usaged memory because the visited nodes and edges are limited. In order to show the effectiveness of the proposed algorithm, it is tested on the city map of Gurgaon. Following, this res ult is compared to the result obtained with dijkstra`s algorithm.


[1] Sara N azari, M. Reza Meybodi, M.ali salehiGh, Sara taghipour, "An Advanced Algorithm for Finding Shortest Path in Car Navigation System," IEEE/ACS International Conference on Computer Systems and Applications, 2008
[2] Liang Dai,"Fast Shortest Path Algorithm for Road Network and Implementation", Carleton Honours PROJE CT,2005.
[3] Syarifah Teh Nadhiah bt Syed Mohamad Nor, “Finding The Minimum Path Using Dijkastra’s Algorithm, Universiti Teknologi MARA , 2007.
[4] Aartsen - prof.dr. J. van Leeuwen Copromotor, dr. J.H. Verriet," Route planning Algorithm for Car navigation",I.C.M 2004.

Shortest path, Geometrical figures, Car Navigation System .