CNS using restricted space algorithms for finding a shortest path

Megha Gupta; Mohit Dua; Narendra Kumar

doi:https://doi.org/10.14445/22315381/IJETT-V2I1P204

Research Article | Open Access | Download PDF

Volume 2 | Issue 1 | Year 2011 | Article Id. IJETT-V2I1P204 | DOI : https://doi.org/10.14445/22315381/IJETT-V2I1P204

CNS using restricted space algorithms for finding a shortest path

Megha Gupta, Mohit Dua , Narendra Kumar

Citation :

Megha Gupta, Mohit Dua , Narendra Kumar, "CNS using restricted space algorithms for finding a shortest path," International Journal of Engineering Trends and Technology (IJETT), vol. 2, no. 1, pp. 49-54, 2011. Crossref, https://doi.org/10.14445/22315381/IJETT-V2I1P204

Abstract

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.

Keywords

Shortest path, Geometrical figures, Car Navigation System .

References

[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.