Johnson 全源最短路 Johnson 和 Floyd 一样是能求出无负环图上任意两点间最短路径的算法。 引入 求任意两点间的最短路可以通过枚举起点,跑 \(n\) 次 SPFA 来解决,时间复杂度是 \(O(n^2 m)\) 的,也可以用 Floyd 解决,复杂度为 \(O(n^3)\)。 或