(Publisher of Peer Reviewed Open Access Journals)

International Journal of Advanced Computer Research (IJACR)

ISSN (Print):2249-7277    ISSN (Online):2277-7970
Volume-3 Issue-13 December-2013
Full-Text PDF
Paper Title : Search the Set of Shorter Paths Using Graph Reduction Technique
Author Name : Tarak Nath Paul, Abhoy Chand Mondal
Abstract :

The beauty of this paper is to clip a Graph provided by Geographic Information System (GIS) into levels (called Levelled Graph), and find the set of shorter paths with source at the very beginning level and destination node as the leaf nodes in the above level. This paper will formulate an algorithm which will provide other shorter paths from source to destination and with the help of Genetic Algorithm (GA) the proposed algorithm is verified. The graph may represent network lines for transferring packets, pipeline to transfer liquid and it may be transportation lines. The proposed algorithm discovers the shortest path and other shorter paths from source to destination with lesser traffic. The selection of node is done using GIS because it is capable enough to express the connectivity of node with one another. The proposed algorithm is compared with Dijksra’s Algorithm and the results are satisfactory. Simulated results are formulated using Matlab. The result assures the potential of the Algorithm.

Keywords : Geospatial Information System, Shortest Path Algorithm, Routing, Graph, Genetic Algorithm, Chromosome, Mutation and Fitness Criteria.
Cite this article : Tarak Nath Paul, Abhoy Chand Mondal, " Search the Set of Shorter Paths Using Graph Reduction Technique " , International Journal of Advanced Computer Research (IJACR), Volume-3, Issue-13, December-2013 ,pp.184-192.