论文标题
Bellman福音对于最短的跳跃路径是最佳的
Bellman-Ford is optimal for shortest hop-bounded paths
论文作者
论文摘要
本文是关于在边缘加权图中最多使用$ h $边缘找到最短的$ s $ -t $路径的问题。 Bellman-福音算法以$ O（hm）$时间解决此问题，其中$ m $是边缘的数量。我们表明，在流行的细颗粒复杂性假设下，这一运行时间是最佳的，直到多个合理因素。 更具体地说，我们表明，在APSP假设下，无法在非导向边缘权重的无向图中更快地解决问题。该下限甚至仅限于任意密度的图和o（\ sqrt {m}）$的任意$ h \。此外，在更强的假设下，即最小卷积假设，我们可以消除O（\ sqrt {m}）$中的限制$ h \。换句话说，$ o（hm）$在参数的整个空间$ h $，$ m $和$ n $的整个空间中都很紧，其中$ n $是节点的数量。 我们的下限可以与负重单源最短路径问题的最近接近线性时间算法形成鲜明对比，这是贝尔曼 - 福音算法的教科书应用。
This paper is about the problem of finding a shortest $s$-$t$ path using at most $h$ edges in edge-weighted graphs. The Bellman--Ford algorithm solves this problem in $O(hm)$ time, where $m$ is the number of edges. We show that this running time is optimal, up to subpolynomial factors, under popular fine-grained complexity assumptions. More specifically, we show that under the APSP Hypothesis the problem cannot be solved faster already in undirected graphs with non-negative edge weights. This lower bound holds even restricted to graphs of arbitrary density and for arbitrary $h \in O(\sqrt{m})$. Moreover, under a stronger assumption, namely the Min-Plus Convolution Hypothesis, we can eliminate the restriction $h \in O(\sqrt{m})$. In other words, the $O(hm)$ bound is tight for the entire space of parameters $h$, $m$, and $n$, where $n$ is the number of nodes. Our lower bounds can be contrasted with the recent near-linear time algorithm for the negative-weight Single-Source Shortest Paths problem, which is the textbook application of the Bellman--Ford algorithm.
