Johnson算法
请不要轻易点击标题
一个可以在有负边的图上使用的多源最短路算法
时间复杂度\(O(n \cdot m \cdot log \ m+n \cdot m)\)
空间复杂度\(O(n+m)\)
这个神奇的算法综合利用了Dijkstra算法和Bellman-Ford算法(不要慌,虽然有负边但Dijkstra可以跑!)
在开始讲解之前，我们将其与floyd进行比较
\(floyd:\)
时间复杂度\(O(n^3)\)
空间复杂度\(O(n^2)\)
可以看出，\(floyd\)复杂度与\(m\)无关 , 可见\(floyd\)适用于稠密图的最短路，而\(Johnson\)算法则是适用于稀疏图最短路
\[\ \]
\[\ \]
\[ \ \]
\[ \ \]
我对该算法的理解
\(Johnson\)算法
限制条件:没有负环即可
在有负权边的图上，\(Dijkstra\)的转移受到限制，我们需要进行一定处理
核心 : 将边权\(reweight\)，保证边权非负后，即可跑\(n\)遍\(Dijkstra\),复杂度稳定\(n \cdot m \cdot log \ m\)(相较于SPFA来说稳定很多)
\[\ \]
Reweight过程
1.建立超级源点0号节点，向\(1 - n\)号节点建立边权为0的有向边
2.利用Bellman-Ford(或SPFA)求得\(dis[0][1..n]\)
3.将边\((u,v,w)\)加上\(dis[0][u]-dis[0][v]\)
4.将Dijkstra得到的路径\(dis[u][v]\)加上\(dis[0][v]-dis[0][u]\)还原
\[\ \]
关于Reweight的正确性
----\(Step 3.\)根据三角不等式\(dis[v]<=dis[u]+w\),移项得到\(w+dis[u]-dis[v] \ge 0\),故Reweight后边权非负
----\(Step4.\)对于一条最短路\(\lbrace p_1,p_2,..,p_k\rbrace\),Reweight后更改的权值即\(dis[p1]-dis[p2]+dis[p2]-dis[p3]...-dis[p_k]\)
即\(dis[0][v]-dis[0][u]\)
----更改后 路径保留的完整性 : 由于对于任意一条路径\(dis[u][v]\),它更改的值都是一个常量\(dis[0][v]-dis[0][u]\)，无论路径如何变更，都不影响这个常量的存在，所以原来的最短路依然保留
(当然我的证明含糊如放屁)
所以我们可以直接用这个算法解决一些特殊的问题