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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An efficient dynamic model for solving the shortest path problem


    Beteiligte:
    Nazemi, Alireza (Autor:in) / Omidi, Farahnaz (Autor:in)


    Erscheinungsdatum :

    2012-07-11


    Format / Umfang :

    19 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch







    Dynamic Programming Approaches for Solving Shortest Path Problem in Transportation: Comparison and Application

    Li, Xuan / Ye, Xiaofei / Lu, Lili | British Library Conference Proceedings | 2020


    Solving partially observable stochastic shortest-path games

    Tomášek, Petr / Horák, Karel / Aradhye, Aditya et al. | BASE | 2021

    Freier Zugriff