AN EFFICIENT GENETIC ALGORITHM BASED METHOD FOR FINDING K SHORTEST AND LONGEST PATHS IN AN UNDIRECTED GRAPH

Abstract

This paper addresses genetic algorithm based method to find k shortest and longest path of a graph. The k-shortest path problem is a generalisation of the shortest path problem in graph theory. It has applications in areas like network routing and multi-object tracking. The longest path problem, on the other hand, is a generalisation of the Hamiltonian path problem. It is used in finding the critical path, among other things. This has applications in circuit design, planning and scheduling. The proposed genetic algorithm based method has been applied to both problems and the conditions which yield the maximum number of paths are determined. The proposed method is efficient to find out better quality path. Comparison with a traditional algorithm is made to judge the effectiveness of the approach