首页 / 算法 / Johnson算法:多源最短路算法
Johnson算法:多源最短路算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Johnson算法:多源最短路算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1199字，纯文字阅读大概需要2分钟。
内容图文
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://www.cnblogs.com/chasedeath/p/11378943.html
内容总结
以上是互联网集市为您收集整理的Johnson算法:多源最短路算法全部内容，希望文章能够帮你解决Johnson算法:多源最短路算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。