Search the Set of Shorter Paths Using Graph Reduction Technique

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.