An applicable method for solving the shortest path problems

被引：15
|
作者：
Zamirian, M. [1 ]
Farahi, M. H. [1 ]
Nazemi, A. R. [1 ]
机构：
[1] Ferdowsi Univ Mashhad, Dept Math, Mashhad, Iran
来源：
APPLIED MATHEMATICS AND COMPUTATION | 2007年 / 190卷 / 02期
关键词：
shortest path; optimal control problem; measure theory; linear programming;
D O I：
10.1016/j.amc.2007.02.057
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A theorem of Hardy, Littlewood, and Polya, first time is used to find the variational form of the well known shortest path problem, and as a consequence of that theorem, one can find the shortest path problem via quadratic programming. In this paper, we use measure theory to solve this problem. The shortest path problem can be written as an optimal control problem. Then the resulting distributed control problem is expressed in measure theoretical form, in fact an infinite dimensional linear programming problem. The optimal measure representing the shortest path problem is approximated by the solution of a finite dimensional linear programming problem. (c) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码：1479 / 1486
页数：8
相关论文
共 50 条
  • [21] A Minimum Resource Neural Network Framework for Solving Multiconstraint Shortest Path Problems
    Zhang, Junying
    Zhao, Xiaoxue
    He, Xiaotao
    IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, 2014, 25 (08) : 1566 - 1582
  • [22] Solving the shortest path tour problem
    Festa, P.
    Guerriero, F.
    Lagana, D.
    Musmanno, R.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 230 (03) : 464 - 474
  • [23] An exact bidirectional A⋆ approach for solving resource-constrained shortest path problems
    Thomas, Barrett W.
    Calogiuri, Tobia
    Hewitt, Mike
    NETWORKS, 2019, 73 (02) : 187 - 205
  • [24] Output-threshold coupled neural network for solving the shortest path problems
    ZHANG Junying
    Computer Department
    Institute of Computer Science
    Department of Electrical and Computer Engineering
    Science in China(Series F:Information Sciences), 2004, (01) : 20 - 33
  • [25] Solving elementary shortest-path problems as mixed-integer programs
    Drexl, Michael
    Irnich, Stefan
    OR SPECTRUM, 2014, 36 (02) : 281 - 296
  • [26] The Role of Convexity for Solving Some Shortest Path Problems in Plane without Triangulation
    Phan Thanh An
    Nguyen Ngoc Hai
    Tran Van Hoai
    INTERNATIONAL CONFERENCE ON MATHEMATICAL SCIENCES AND STATISTICS 2013 (ICMSS2013), 2013, 1557 : 89 - 93
  • [27] Output-threshold coupled neural network for solving the shortest path problems
    Junying Zhang
    Defeng Wang
    Meihong Shi
    Joseph Yue Wang
    Science in China Series F: Information Sciences, 2004, 47 : 20 - 33
  • [28] On Solving the Quadratic Shortest Path Problem
    Hu, Hao
    Sotirov, Renata
    INFORMS JOURNAL ON COMPUTING, 2020, 32 (02) : 219 - 233
  • [29] Value Iteration Algorithm for Solving Shortest Path Problems with Homology Class Constraints
    He, Wenbo
    Huang, Yunshen
    Qie, Jinran
    Zeng, Shen
    2023 62ND IEEE CONFERENCE ON DECISION AND CONTROL, CDC, 2023, : 8400 - 8405
  • [30] An Approximate Algorithm for Solving Shortest Path Problems for Mobile Robots or Driver Assistance
    Li, Fajie
    Klette, Reinhard
    Morales, Sandino
    2009 IEEE INTELLIGENT VEHICLES SYMPOSIUM, VOLS 1 AND 2, 2009, : 42 - 47
12345