可達性演算法

所謂的“可達性演算法”可以解決 m 條邊的圖上的最短路徑問題（即，在兩個給定節點之間找到圖的測地線的問題），對於非迴圈有向圖，只需 -邊圖 中的 步。此演算法允許路徑中，以與其方向相反的方向遍歷的邊具有負長度。

沒有其他演算法能有更好的複雜度，因為任何其他演算法至少需要檢查每條邊，而這本身就需要 步。