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 条

[31] Design of Secondary Circuits of Distribution Networks using Clustering and Shortest Path Algorithms [J].

Cabrera-Celi, Gabriela C. ;

Novoa-Guaman, Edison G. ;

Vasquez-Miranda, Paul F. .

2017 IEEE PES INNOVATIVE SMART GRID TECHNOLOGIES CONFERENCE - LATIN AMERICA (ISGT LATIN AMERICA), 2017,

[32] A One-Layer Dual Neural Network with a Unipolar Hard-Limiting Activation Function for Shortest-Path Routing [J].

Liu, Qingshan ;

Wang, Jun .

ARTIFICIAL NEURAL NETWORKS-ICANN 2010, PT II, 2010, 6353 :498-+

[33] On shortest path games [J].

Fragnelli, V ;

García-Jurado, I ;

Méndez-Naya, L .

MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2000, 52 (02) :251-264

[34] On the Shortest Path Game [J].

Darmann, Andreas ;

Pferschy, Ulrich ;

Schauer, Joachim .

DISCRETE APPLIED MATHEMATICS, 2017, 217 :3-18

[35] A Small-Gain Analysis for an All-Pairs Shortest-Path Algorithm: Global Exponential Input-to-State Stability [J].

Mo, Yuanqiu ;

Yu, Lanlin ;

Du, Haibo .

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, 2024, 11 (02) :821-830

[36] Privacy-preserving Parallel Computation of Shortest Path Algorithms with Low Round Complexity [J].

Anagreh, Mohammad ;

Laud, Peeter ;

Vainikko, Eero .

PROCEEDINGS OF THE 8TH INTERNATIONAL CONFERENCE ON INFORMATION SYSTEMS SECURITY AND PRIVACY (ICISSP), 2021, :37-47

[37] The multiple shortest path problem with path deconfliction [J].

Hughes, Michael S. ;

Lunday, Brian J. ;

Weir, Jeffrey D. ;

Hopkinson, Kenneth M. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 292 (03) :818-829

[38] Stochastic shortest path games [J].

Patek, SD ;

Bertsekas, DP .

SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1999, 37 (03) :804-824

[39] Genetic Algorithms for Solving Shortest Path Problem in Maze-Type Network with Precedence Constraints [J].

JunWoo Kim ;

Soo Kyun Kim .

Wireless Personal Communications, 2019, 105 :427-442

[40] Neutrosophic Shortest Path Problem [J].

Kumar, Ranjan ;

Edaltpanah, S. A. ;

Jha, Sripati ;

Broumi, Said ;

Dey, Arindam .

NEUTROSOPHIC SETS AND SYSTEMS, 2018, 23 :5-15

← 1 2 3 4 5 →