Highlights ► A dynamic model for solving the shortest path problem is proposed. ► The basic idea is to replace the shortest path problem by a LP. ► The proposed dynamic model is proved to be stable in the sense of Lyapunov. ► The model is globally convergent to an exact optimal solution of the original problem. ► The validity of the model is demonstrated by using some examples.
Abstract 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.
An efficient dynamic model for solving the shortest path problem
2012-07-11
19 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
An efficient dynamic model for solving the shortest path problem
Online Contents | 2013
|Efficient Algorithms for Solving the Shortest Covering Path Problem
Online Contents | 1994
|British Library Conference Proceedings | 2020
|