是否存在具有阈值距离的最短路径算法，超过该距离它不会尝试计算？

Question

我想计算所有 N 对节点之间的最短路径（每个节点大约有 3 个有向边）。重要的细微差别是，如果距离大于某个阈值 (T)，我将不再关心它（就我而言，D_ij>T = ∞）。

所以，一旦我确定 i 到 j 的距离大于阈值，我就不再需要继续寻找确切的值，只要知道它大于阈值即可。

是否已经有一个最短路径算法结合了这样的阈值信息来使过程更高效？

请注意，对于 D_ij < T 的所有情况，我确实关心 D 的确切值。

Answer 1

由于您需要所有节点对之间的距离，请查看 Floyd-Warshall 算法。

运行 FW 算法如何并在完成后将结果截断为 T（运行时间 O(N^3) 然后截断）？

如果您的图很大（N 大），那么对于每个节点 3 条边，它非常稀疏。在这种情况下，更好的选择是对每个可能的起始顶点执行 Dijkstra 方法，在这种情况下，您可以在处理节点的累积距离超过 T 时立即中止该方法。

作为替代方案，从启发式解决问题改为解决等同于最短路径问题的线性规划 (LP)，请参见例如.

在这种情况下，您的问题只是一个一般的最短路径问题（每个节点对一个 LP），但有一个额外的约束：

objective function cost <= T  (+)

鉴于每个节点都存在有向边，原始问题的相应线性规划——对于每个节点对——将始终是可行的。因此，在您的情况下，如果某个节点对的 LP 不可行，则意味着找不到满足您的附加约束 (+) 的路径。随后，该对的最短路径，比如 D_ij，大于 T，即 D_ij>T.

解决 LP:s 与最短路径问题相关的问题通常可以非常快（如果有一个好的 LP 求解器），也可以找到不可行性。 w.r.t，也许这对您来说是一个替代方案。启发式方法。

Is there a shortest path algorithm with a threshold distance, beyond which it does not try to compute?