EFFICIENT SHORTEST-PATH SIMPLEX ALGORITHMS

被引：20

作者：

GOLDFARB, D ^{[1
]}

HAO, JX ^{[1
]}

KAI, SR ^{[1
]}

机构：

[1] GTE LABS INC, WALTHAM, MA 02254 USA

来源：

OPERATIONS RESEARCH | 1990年 / 38卷 / 04期

关键词：

D O I：

10.1287/opre.38.4.624

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the specialization of the primal simplex algorithm to the problem of finding a tree of directed shortest paths from a given node to all other nodes in a network of n nodes or finding a directed cycle of negative length. Two efficient variants of this shortest path simplex algorithm are analyzed and shown to require at most (n - 1)(n - 2)/2 pivots and O(n3) time.

引用

页码：624 / 628

页数：5

共 50 条

[1] A COMPUTATIONAL STUDY OF EFFICIENT SHORTEST-PATH ALGORITHMS
HUNG, MS
DIVOKY, JJ
COMPUTERS & OPERATIONS RESEARCH, 1988, 15 (06) : 567 - 576
[2] Shortest-path reconstruction algorithms
Khoong, C.M., 1600, (36):
[3] SHORTEST-PATH RECONSTRUCTION ALGORITHMS
KHOONG, CM
COMPUTER JOURNAL, 1993, 36 (06): : 588 - 592
[4] SHORTEST-PATH ALGORITHMS - COMPARISON
GOLDEN, B
OPERATIONS RESEARCH, 1976, 24 (06) : 1164 - 1168
[5] FASTER ALGORITHMS FOR THE SHORTEST-PATH PROBLEM
AHUJA, RK
MEHLHORN, K
ORLIN, JB
TARJAN, RE
JOURNAL OF THE ACM, 1990, 37 (02) : 213 - 223
[6] SHORTEST-PATH ALGORITHMS - TAXONOMY AND ANNOTATION
DEO, N
PANG, CY
NETWORKS, 1984, 14 (02) : 275 - 323
[7] AN EMPIRICAL SURVEY OF SHORTEST-PATH ALGORITHMS
MOFFAT, A
NEW ZEALAND OPERATIONAL RESEARCH, 1983, 11 (02): : 153 - 163
[8] PARALLEL SHORTEST-PATH AUCTION ALGORITHMS
POLYMENAKOS, LC
BERTSEKAS, DP
PARALLEL COMPUTING, 1994, 20 (09) : 1221 - 1247
[9] AN APPRAISAL OF SOME SHORTEST-PATH ALGORITHMS
DREYFUS, SE
OPERATIONS RESEARCH, 1969, 17 (03) : 395 - &
[10] GREEDY PARTITIONED ALGORITHMS FOR THE SHORTEST-PATH PROBLEM
ADAMSON, P
TICK, E
INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING, 1992, 20 (04) : 271 - 298

← 1 2 3 4 5 →