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 条
  • [21] Reversible Programming Techniques for Shortest-Path Algorithms
    Guo, Lanying
    Peng, Chao
    Chen, Siyuan
    He, Cheng
    2018 IEEE 37TH INTERNATIONAL PERFORMANCE COMPUTING AND COMMUNICATIONS CONFERENCE (IPCCC), 2018,
  • [22] Parallel algorithms for solving aggregated shortest-path problems
    Romeijn, HE
    Smith, RL
    COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (10-11) : 941 - 953
  • [23] Parametric Shortest-Path Algorithms via Tropical Geometry
    Joswig, Michael
    Schroter, Benjamin
    MATHEMATICS OF OPERATIONS RESEARCH, 2022, 47 (03) : 1 - 17
  • [24] NEW POLYNOMIAL SHORTEST-PATH ALGORITHMS AND THEIR COMPUTATIONAL ATTRIBUTES
    GLOVER, F
    KLINGMAN, DD
    PHILLIPS, NV
    SCHNEIDER, RF
    MANAGEMENT SCIENCE, 1985, 31 (09) : 1106 - 1128
  • [25] Engineering Label-Constrained Shortest-Path Algorithms
    Barrett, Chris
    Bisset, Keith
    Holzer, Martin
    Konjevod, Goran
    Marathe, Madhav
    Wagner, Dorothea
    SHORTEST PATH PROBLEM, 2009, 74 : 309 - +
  • [26] Engineering label-constrained shortest-path algorithms
    Barrett, Chris
    Bisset, Keith
    Holzer, Martin
    Konjevod, Goran
    Marathe, Madhav
    Wagner, Dorothea
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2008, 5034 : 27 - +
  • [27] PERFORMANCE OF SHORTEST-PATH ALGORITHMS IN NETWORK FLOW PROBLEMS
    DIVOKY, JJ
    HUNG, MS
    MANAGEMENT SCIENCE, 1990, 36 (06) : 661 - 673
  • [28] PROGRAM REALIZATION OF SHORTEST-PATH ALGORITHMS IN TRANSPORTATION MIS
    ANDROSOV, SM
    GLUZMAN, BY
    OSLON, VA
    AUTOMATION AND REMOTE CONTROL, 1987, 48 (09) : 1246 - 1250
  • [29] PARAMETRIC SHORTEST-PATH ALGORITHMS WITH AN APPLICATION TO CYCLIC STAFFING
    KARP, RM
    ORLIN, JB
    DISCRETE APPLIED MATHEMATICS, 1981, 3 (01) : 37 - 45
  • [30] A SHORT PATH TO THE SHORTEST-PATH
    LAX, PD
    AMERICAN MATHEMATICAL MONTHLY, 1995, 102 (02): : 158 - 159
12345