BriefGPT.xyz
Jan, 2014
利用低树宽计算所有对最短路径
Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
HTML
PDF
Léon R. Planken, Mathijs M. de Weerdt, Roman P. J. van der Krogt
TL;DR
本论文提出了两种新的算法,用于计算带有实数边权(可能为负数)的有向图的全源最短路径。这两种算法运行时间复杂度为O(n^2w_d),可用于空间和时间推理,比Floyd-Warshall算法和Johnson算法更快,并且具有规划和调度社区的相关性。
Abstract
We present two new and efficient
algorithms
for computing
all-pairs shortest paths
. The
algorithms
operate on
→