$Johnson$ 是用来求带负权不带负环的全源最短路。

1. 新建一个虚拟节点（$0$），从这个点向所有点连权值为 $0$ 的边。
2. 用死了的 $SPFA$ 或 $Bellman-Ford$ 求出以 $0$ 为源点的最短路。
3. 将（$u$，$v$）的边权 $w$ 改为 $w+h_u-h_v$。
4. 以每个点为起点用 $Dijkstra$ 求出最短路。

时间复杂度：$O(nmlogm)$。空间复杂度：$O(nm)$