FINDING THE HIDDEN PATH - TIME-BOUNDS FOR ALL-PAIRS SHORTEST PATHS

被引：72

作者：

KARGER, DR ^{[1
]}

KOLLER, D ^{[1
]}

PHILLIPS, SJ ^{[1
]}

机构：

[1] IBM CORP,ALMADEN RES CTR,SAN JOSE,CA

来源：

SIAM JOURNAL ON COMPUTING | 1993年 / 22卷 / 06期

关键词：

ALL-PAIRS SHORTEST PATHS; WEIGHTED GRAPHS; LOWER BOUND; PATH COMPARISON; ALGORITHM; RANDOM GRAPHS;

D O I：

10.1137/0222071

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The all-pairs shortest-paths problem in weighted graphs is investigated. An algorithm-the Hidden-Paths Algorithm-that finds these paths in time O(m*n + n(2) log n), where m* is the number of edges participating in shortest paths, is presented. The algorithm is a practical substitute for Dijkstra's algorithm. It is argued that m* is likely to be small in practice since m* = O(n log n) with high probability for many probability distributions on edge weights. An Omega (mn) lower bound on the running time of any path-comparison-base algorithm for the all-pairs shortest-paths problem is also proved. Path-comparison-based algorithms form a natural class containing the Hidden-Paths Algorithm, as well as the algorithms off E.W. Dijkstra [Numer.Math., 1 (1959), pp. 269-271] and R.W. Floyd [Comm.ACM, 5 (1962), p. 345]. Lastly, generalized forms of the shortest-paths problem are considered, and it is shown that many of the standard shortest-paths algorithms are effective in this more general setting.

引用

页码：1199 / 1217

页数：19

共 34 条

[1]

ALON N, 1991, 32ND P ANN IEEE S F, P569

[2]

ALON N, 1992, RJ8744 IBM TECH REP

[3]

BLONIARZ PA, 1980, 803 STAT U NEW YORK

[4] MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS [J].