SCALING ALGORITHMS FOR THE SHORTEST PATHS PROBLEM

被引：88

作者：

GOLDBERG, AV ^{[1
]}

机构：

[1] IBM CORP,ALMADEN RES CTR,ARMONK,NY 10504

来源：

SIAM JOURNAL ON COMPUTING | 1995年 / 24卷 / 03期

关键词：

SHORTEST PATHS PROBLEM; GRAPH THEORY; NETWORKS; SCALING;

D O I：

10.1137/S0097539792231179

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We describe a new method for designing scaling algorithms for the single-source shortest paths problem and use this method to obtain an O(root nm log N) algorithm for the problem. (Here n and m are the number of nodes and arcs in the input network and N is essentially the absolute value of the most negative arc length; arc lengths are assumed to be integral.) This improves previous bounds for the problem. The method extends to related problems.

引用

页码：494 / 504

页数：11

共 22 条

[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] ON THE COMPUTATIONAL BEHAVIOR OF A POLYNOMIAL-TIME NETWORK FLOW ALGORITHM [J].