Johnson 算法 https://www.baidu.com/s?ie=UTF-8&wd=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]\), 无论路径如何变更, 都不影响这个常量的存在, 所以原来的最短路依然保留
(当然我的证明含糊如放屁)
所以我们可以直接用这个算法解决一些特殊的问题 https://ac.nowcoder.com/acm/contest/920/C
来源: http://www.bubuko.com/infodetail-3162243.html