我想计算所有N个节点对之间的最短路径（每个节点有大约3个有向边）。重要的细微差别在于，如果距离大于某个阈值（T），我就不再在乎它了（就我而言，D_ij> T =∞）。是否存在一个阈值距离的最短路径算法，超出此算法它不会计算？
所以，一旦我确定从i到j的距离大于阈值，我不再需要继续寻找确切的值，只是要知道它大于阈值。
是否已有一条最短路径算法合并了此类阈值信息以使过程更高效？
注意，对于所有案件中，D_ij < T I不关心D.
既然你要对所有节点之间距离的精确值，看弗洛伊德 - Warshall算法。
https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm
如何运行FW算法，并对其做（运行时间O（N^3），然后截断）后仅仅截断结果与T？
如果你的图很大（N大），那么对于每个节点的3条边来说，它相当稀疏。在这种情况下，更好的选择是执行Dijkstra的方法，对每个可能的起始顶点，在这种情况下，你可以立即中止该法作为处理节点的累积距离超过T.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
作为一种替代方法，从启发式解决问题转变为求解等价于最短路径问题的线性规划（LP），参见例如How to formulate LP for shortest path problems?。
在这种情况下，你的问题只是一般最短路径问题（一个LP每个节点对），但有一个附加的约束：
objective function cost <= T (+)
鉴于目前从每个节点存在有向边时，原始问题对应的LP ---对于每个节点对---总是可行的。因此，就你而言，如果某个节点对的LP不可行，则意味着找不到满足附加约束（+）的路径。随后，该对的最短路径，比如D_ij，大于T，即D_ij> T。解决与最短路径问题有关的LP通常可以非常快（给定一个良好的LP求解器），也可以用于寻找不可行性。也许这可以替代你，w.r.t.启发式方法。
谢谢。我将探索截断Dijkstra的方法和LP解决方案，看看哪些性能更好。 N = 100000，性能非常关键（运行数十万次，每次使用不同的权重集）。 – Shimi
欢迎您。我对结果很感兴趣，所以如果你不介意的话，请在你的研究结果中添加一条评论（如果你设法严格回答你自己的问题，甚至可以回答）。祝你好运！ – dfri
@Shimi另一个评论：当使用LP方法时，请注意，许多LP求解器允许Simplex方法的“热启动”，这是因为基本可行解（BFS）可以用作相关问题的良好（甚至非最优）初始BFS。这些问题与增加的约束条件有关，然后通过选择双重单纯形法可以保证在另一个问题中使用BFS的可行性（因为原始数据中的另一个约束条件只是双数据集中的另一个变量）。可能适用于你的研究案例。 – dfri
如果您对问题的答案满意，请将其标记为已回答。否则，请提供反馈或改进您的问题，看看是否有其他人可以回答。或者可能尝试将它移动到math.stackexchange以获得更多的关注。 – dfri