Johnson 全源最短路径算法

Johnson 算法是一种用于求解给定加权有向图中所有节点对之间的最短路径的算法。它可以处理具有负权边的图，并且时间复杂度为O(n^2logn+m*n)，其中n是图中节点数，m是边数。

算法的基本思想是通过将每条边的权重增加一个非负的常数使得所有边权变为非负，然后使用Dijkstra算法或Bellman-Ford算法求解每个节点到其他节点的最短路径。最后，通过恢复原始权重来得到最终的最短路径。

具体来说，算法的步骤如下：

1. 对原始图进行转换，增加一个新的节点s，并添加从s到所有其他节点的边，边权均为0。

2. 使用Bellman-Ford算法计算s到所有其他节点的最短路径，如果存在负环则停止算法。

3. 对转换后的图进行边权重的修正，对于边(u, v)，设其原始权重为w(u, v)，则修正后的权重为w'(u, v) = w(u, v) + h(u) - h(v)，其中h(u)和h(v)分别为Bellman-Ford算法中计算得到的s到u和s到v的最短路径长度。

4. 对于修正后的图，使用Dijkstra算法求解每个节点到其他节点的最短路径，注意在计算路径长度时需要根据修正前的权重计算。

5. 根据修正后的权重和Dijkstra算法计算得到的最短路径长度，恢复原始权重，得到最终的最短路径。

Johnson算法的核心在于通过将边权重修正为非负来避免负权边对Dijkstra算法的影响，同时通过Bellman-Ford算法计算每个节点到源点的最短路径来计算修正后的权重。但是，由于需要进行两次最短路径的计算，因此算法的时间复杂度比较高。