A HEURISTIC IMPROVEMENT OF THE BELLMAN-FORD ALGORITHM

被引：88
作者：
GOLDBERG, AV [1 ]
RADZIK, T [1 ]
机构：
[1] CORNELL UNIV,SORIE,ITHACA,NY 14853
来源：
APPLIED MATHEMATICS LETTERS | 1993年 / 6卷 / 03期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1016/0893-9659(93)90022-F
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We describe a new shortest paths algorithm. Our algorithm achieves the same O(nm) worst-case time bound as Bellman-Ford algorithm but is superior in practice.
引用
收藏
页码：3 / 6
页数：4
相关论文
共 12 条
  • [1] [Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265
  • [2] Bellman R., 1958, Q APPL MATH, V16, P87, DOI [10.1090/qam/102435, DOI 10.1090/QAM/102435]
  • [3] Dijkstra EW., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390
  • [4] Ford L., 1962, FLOWS NETWORKS, V71, P1059, DOI 10.2307/2311955
  • [5] FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS
    FREDMAN, ML
    TARJAN, RE
    [J]. JOURNAL OF THE ACM, 1987, 34 (03) : 596 - 615
  • [6] LEVIT BJ, 1972, NELENEINYE SETEVYE T
  • [7] Moore E. F., 1959, P INT S THEOR SWITCH, P285
  • [8] SHORTEST-PATH METHODS - COMPLEXITY, INTERRELATIONS AND NEW PROPOSITIONS
    PALLOTTINO, S
    [J]. NETWORKS, 1984, 14 (02) : 257 - 267
  • [9] Pape U., 1974, Mathematical Programming, V7, P212, DOI 10.1007/BF01585517
  • [10] PROPERTIES OF LABELING METHODS FOR DETERMINING SHORTEST-PATH TREES
    SHIER, DR
    WITZGALL, C
    [J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS, 1981, 86 (03): : 317 - 330
12