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 [J].

Ardizzoni, Stefano ;

Consolini, Luca ;

Laurini, Mattia ;

Locatelli, Marco .

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 [J].

Petrovan, Adrian ;

Pop, Petrica ;

Sabo, Cosmin ;

Zelina, Ioana .

EXPERT SYSTEMS WITH APPLICATIONS, 2023, 215

[23] Distributed algorithms from arboreal ants for the shortest path problem [J].

Garg, Shivam ;

Shiragur, Kirankumar ;

Gordon, Deborah M. ;

Charikar, Moses .

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 [J].

Chakraborty, Sourav ;

Fischer, Eldar ;

Lachish, Oded ;

Yuster, Raphael .

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 [J].

WELLER, T ;

HAJEK, B .

IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (07) :862-863

[26] Solving Stochastic Shortest Distance Path Problem by Using Genetic Algorithms [J].

Ahmadi, Ehsan ;

Suer, Gursel A. ;

Al-Ogaili, Farah .

CYBER PHYSICAL SYSTEMS AND DEEP LEARNING, 2018, 140 :79-86

[27] Computational Results on Some Shortest Path Problems with Side Constraints [J].

Kobayashi, Kazuhiro .

2008 PROCEEDINGS OF SICE ANNUAL CONFERENCE, VOLS 1-7, 2008, :923-927

[28] Extensions of labeling algorithms for multi-objective uncertain shortest path problems [J].

Raith, Andrea ;

Schmidt, Marie ;

Schoebel, Anita ;

Thom, Lisa .

NETWORKS, 2018, 72 (01) :84-127

[29] New dynamic programming algorithms for the resource constrained elementary shortest path problem [J].

Righini, Giovanni ;

Salani, Matteo .

NETWORKS, 2008, 51 (03) :155-170

[30] Accelerated label setting algorithms for the elementary resource constrained shortest path problem [J].

Boland, N ;

Dethridge, J ;

Dumitrescu, I .

OPERATIONS RESEARCH LETTERS, 2006, 34 (01) :58-68

← 1 2 3 4 5 →