首页 / 算法 / 【图论】Johnson算法
【图论】Johnson算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【图论】Johnson算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含580字,纯文字阅读大概需要1分钟。
内容图文
![【图论】Johnson算法](/upload/InfoBanner/zyjiaocheng/606/188c4eed9c594b52a356830e7b6c151f.jpg)
适用于求解没有负环的全源最短路,最坏时间复杂度 \(O(nm\log m)\) 比Floyd要优秀(但是Floyd可以找出负环)。
在没有负权边时,使用n次单源最短路Dijkstra代替即可。
算法流程:
1、新建一个虚拟节点(编号为n+1),向[1,n]连接一条边权为0的虚拟边。
2、从n+1号节点开始跑一次队列优化BellmanFord,得到从n+1号虚拟节点到节点i的最短路hgt[i],假如存在负环,则无法求解。
3、删除虚拟节点和虚拟边(也可以直接选择忽视他们)
4、把每条非虚拟边(u,v,w)改为(u,v,w+hgt[u]-hgt[v])
5、对于每个点i属于[1,n],跑一次Dijkstra,得到从i节点到[1,n]的非虚拟节点的最短路dis[j]。
6、原本的[i,j]的最短路为dis[j]+hgt[i]-hgt[j]
内容总结
以上是互联网集市为您收集整理的【图论】Johnson算法全部内容,希望文章能够帮你解决【图论】Johnson算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。