A gene-constrained genetic algorithm for solving shortest path problem

In this paper, a gene-constrained genetic algorithm (G-C GA) to solve shortest path problem is proposed. In this genetic algorithm (GA), gene is constrained to ensure that each chromosome represents a feasible path without loop during the whole process of search. Contrasting with other genetic algorithm for SP problem, our algorithm can improve the searching capacity with a more accurate solution and more rapid speed of convergence. The G-C GA is more general and flexible no matter in a directed graph or in an undirected graph and it provides the foundation for more complicated shortest path problems.