K SHORTEST AND LONGEST PATHS IN AN UNDIRECTED GRAPH: AN EFFECTIVE GENETIC ALGORITHM-BASED METHOD

Abstract

This study tackles evolutionary algorithm based method to identify the shortest and longest path of a graph. The k-shortest path problem is an extension of the shortest path problem in graph theory. Applications for it include multi-object tracking and network routing. In contrast, the Hamiltonian path problem is a generalization of the longest path issue. Among other things, it is employed to determine the critical path. This has uses in scheduling, planning, and circuit design. Both issues have been solved using the suggested genetic algorithm-based approach, and the circumstances that provide the greatest number of possible paths have been identified. The suggested approach is effective at identifying higher-quality routes. A comparison with a conventional algorithm is used to assess the method's efficacy.