A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs
A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs
复制标题
实加权稀疏图的更快的全对最短路径算法
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Seth Pettie
中科院分区：
文献类型：
--
作者：
Seth Pettie
提出了一种求解任意实权有向图的快速全对最短路径算法。该算法在基本的比较加法模型中工作，运行时间为O(mn+n2 log log n)，其中m和n分别是边和顶点的数量。当m = 0 （n log n）时，这比Johnson的算法（对于任意边权）和Dijkstra的算法（对于正边权）要快得多，并且匹配Hagerup的APSP算法的运行时间，后者假设整数边权和更强大的计算模型。
We present a faster all-pairs shortest paths algorithm for arbitrary real-weighted directed graphs. The algorithm works in the fundamental comparison-addition model and runs in O(mn+n2 log log n) time, where m and n are the number of edges & vertices, respectively. This is strictly faster than Johnson's algorithm (for arbitrary edge-weights) and Dijkstra's algorithm (for positive edge-weights) when m = o(n log n) and matches the running time of Hagerup's APSP algorithm, which assumes integer edge-weights and a more powerful model of computation.