可达性算法

所谓的“可达性算法”可以解决 m 条边的图上的最短路径问题（即，在两个给定节点之间找到图的测地线的问题），对于非循环有向图，只需 -边图 中的 步。此算法允许路径中，以与其方向相反的方向遍历的边具有负长度。

没有其他算法能有更好的复杂度，因为任何其他算法至少需要检查每条边，而这本身就需要 步。