An efficient dynamic model for solving the shortest path problem

摘要

The shortest path problem is the classical combinatorial optimization problem arising in numerous planning and designing contexts. This paper presents a neural network model for solving the shortest path problems. The main idea is to replace the shortest path problem with a linear programming (LP) problem. According to the saddle point theorem, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle, the equilibrium point of the proposed neural network is proved to be equivalent to the optimal solution of the original problem. It is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the shortest path problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.