Johnson算法

请不要轻易点击标题

一个可以在有负边的图上使用的多源最短路算法

时间复杂度\(O(n \cdot m \cdot log \ m+n \cdot m)\)

空间复杂度\(O(n+m)\)

这个神奇的算法综合利用了Dijkstra算法和Bellman-Ford算法(不要慌,虽然有负边但Dijkstra可以跑!)

在开始讲解之前，我们将其与floyd进行比较

时间复杂度\(O(n^3)\)

空间复杂度\(O(n^2)\)

可以看出，\(floyd\)复杂度与\(m\)无关 , 可见\(floyd\)适用于稠密图的最短路，而\(Johnson\)算法则是适用于稀疏图最短路

\[\ \]

\[ \ \]

我对该算法的理解

限制条件:没有负环即可

在有负权边的图上，\(Dijkstra\)的转移受到限制，我们需要进行一定处理

核心 : 将边权\(reweight\)，保证边权非负后，即可跑\(n\)遍\(Dijkstra\),复杂度稳定\(n \cdot m \cdot log \ m\)(相较于SPFA来说稳定很多)

\[\ \]

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]\)，无论路径如何变更，都不影响这个常量的存在，所以原来的最短路依然保留

~~(当然我的证明含糊如放屁)~~

所以我们可以直接用这个算法解决一些特殊的问题

巴特西