ON THE EQUIVALENCE BETWEEN SOME SHORTEST-PATH ALGORITHMS

被引：3
作者：
SHERALI, HD
机构：
[1] Department of Industrial and Systems Engineering, Virginia Polytechnic Institute, State University, Blacksburg
来源：
OPERATIONS RESEARCH LETTERS | 1991年 / 10卷 / 02期
关键词：
SHORTEST PATH PROBLEM; DYNAMIC PROGRAMMING; PARTITIONED SHORTEST PATH ALGORITHM; MOORE ALGORITHM;
D O I：
10.1016/0167-6377(91)90088-7
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we show the equivalence between a particular implementation of the Partitioned Shortest Path (PSP) algorithm, Moore's algorithm, and a dynamic programming approach with an appropriate state space and decision space reduction, when applied to a problem of determining a shortest simple path from a given node to all the nodes in a network having arbitrary costs but with no negative cost circuits. This equivalence provides insights into the PSP method, shows that Moore's algorithm has a polynomial-time implementation, and facilitates by definition the proofs of various properties.
引用
收藏
页码：61 / 65
页数：5
相关论文
共 50 条
  • [21] Solution Algorithms for the Bounded Acceleration Shortest Path Problem
    Ardizzoni, Stefano
    Consolini, Luca
    Laurini, Mattia
    Locatelli, Marco
    [J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2023, 68 (03) : 1910 - 1917
  • [22] Novel two-level hybrid genetic algorithms based on different Cayley-type encodings for solving the clustered shortest-path tree problem
    Petrovan, Adrian
    Pop, Petrica
    Sabo, Cosmin
    Zelina, Ioana
    [J]. EXPERT SYSTEMS WITH APPLICATIONS, 2023, 215
  • [23] Distributed algorithms from arboreal ants for the shortest path problem
    Garg, Shivam
    Shiragur, Kirankumar
    Gordon, Deborah M.
    Charikar, Moses
    [J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2023, 120 (06)
  • [24] TWO-PHASE ALGORITHMS FOR THE PARAMETRIC SHORTEST PATH PROBLEM
    Chakraborty, Sourav
    Fischer, Eldar
    Lachish, Oded
    Yuster, Raphael
    [J]. 27TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2010), 2010, 5 : 167 - 178
  • [25] AN OPTIMAL SHORTEST-PATH ROUTING POLICY FOR NETWORK COMPUTERS WITH REGULAR MESH-CONNECTED TOPOLOGIES - COMMENT
    WELLER, T
    HAJEK, B
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (07) : 862 - 863
  • [26] Solving Stochastic Shortest Distance Path Problem by Using Genetic Algorithms
    Ahmadi, Ehsan
    Suer, Gursel A.
    Al-Ogaili, Farah
    [J]. CYBER PHYSICAL SYSTEMS AND DEEP LEARNING, 2018, 140 : 79 - 86
  • [27] Computational Results on Some Shortest Path Problems with Side Constraints
    Kobayashi, Kazuhiro
    [J]. 2008 PROCEEDINGS OF SICE ANNUAL CONFERENCE, VOLS 1-7, 2008, : 923 - 927
  • [28] Extensions of labeling algorithms for multi-objective uncertain shortest path problems
    Raith, Andrea
    Schmidt, Marie
    Schoebel, Anita
    Thom, Lisa
    [J]. NETWORKS, 2018, 72 (01) : 84 - 127
  • [29] New dynamic programming algorithms for the resource constrained elementary shortest path problem
    Righini, Giovanni
    Salani, Matteo
    [J]. NETWORKS, 2008, 51 (03) : 155 - 170
  • [30] Accelerated label setting algorithms for the elementary resource constrained shortest path problem
    Boland, N
    Dethridge, J
    Dumitrescu, I
    [J]. OPERATIONS RESEARCH LETTERS, 2006, 34 (01) : 58 - 68
12345