前置知识
SPFA、Dijkstra.
引文
先是给一道题目：
给定一个包含 n 个结点和 m 条带权边的有向图，求所有点对间的最短路径长度，一条路径的长度定义为这条路径上所有边的权值和。
看到最短路，你也许会想到最短路；
然而发现它居然会有负边，也就是说可能会有负环，你便可能想到 SPFA 或是 Floyd，
但是时间复杂度一个为 \(O(n^2m)\) ，一个为 \(O(n^3)\) ，都不能很快的通过此题，
这便需要我们用到 \(JohnSon\) 全员最短路算法了。
正文
首先我们可以发现，
设 \(dis(x, y)\) 为 \(x\) 与 \(y\) 之间的最短路，
标签：浅谈,JohnSon,短路,路径,SPFA,全源 From： https://www.cnblogs.com/Sengyi/p/17045141.html