论文标题
通过大约成本平衡的指向最短路径
Directed Shortest Paths via Approximate Cost Balancing
论文作者
论文摘要
我们为全对最短路径计算的$ O（nm）$算法提供了$ N $ NODES，$ M $ ARCS和非负整数ARC成本的最短路径计算。这匹配了Thorup \ cite {Thorup1999}所达到的复杂性，对于无向图中的全对问题。主要见解是，最短的路径问题近似平衡的定向成本函数可以与无向情况相似。该算法在$ o（M \ sqrt {n} \ log n）$ PrepRocessing步骤中找到了大致平衡的成本函数。使用这些降低的成本，可以使用Thorup的组件层次结构方法改编的每个最短路径查询以$ O（m）$时间来解决。平衡结果也可以应用于$ \ ell_ \ infty $ -matrix平衡问题。
We present an $O(nm)$ algorithm for all-pairs shortest paths computations in a directed graph with $n$ nodes, $m$ arcs, and nonnegative integer arc costs. This matches the complexity bound attained by Thorup \cite{Thorup1999} for the all-pairs problems in undirected graphs. The main insight is that shortest paths problems with approximately balanced directed cost functions can be solved similarly to the undirected case. The algorithm finds an approximately balanced reduced cost function in an $O(m\sqrt{n}\log n)$ preprocessing step. Using these reduced costs, every shortest path query can be solved in $O(m)$ time using an adaptation of Thorup's component hierarchy method. The balancing result can also be applied to the $\ell_\infty$-matrix balancing problem.
