Johnson 全源最短路径算法学习笔记
2021/10/15 9:14:44
本文主要是介绍Johnson 全源最短路径算法学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Johnson 全源最短路径算法学习笔记
如果你希望得到带互动的极简文字体验,请点这里
我们来学习johnson
Johnson 算法是一种在边加权有向图中找到所有顶点对之间最短路径的方法。它允许一些边权重为负数,但可能不存在负权重循环。它的工作原理是使用Bellman-Ford 算法来计算输入图的转换,该转换去除了所有负权重,从而允许在转换后的图上使用Dijkstra 算法。Johnson 算法是一种在边加权有向图中找到所有顶点对之间最短路径的方法。它允许一些边权重为负数,但可能不存在负权重循环。它的工作原理是使用Bellman-Ford 算法来计算输入图的转换,该转换去除了所有负权重,从而允许在转换后的图上使用Dijkstra 算法。
--维基百科
- 可以发现排序算法中最能够全源的只有Johnson 和 Floyd
最优情况:
全源最短路跑\(n\) 次 Bellman-Ford 算法解决,时间复杂度是\(O(n^2m)\),原始是Floyd的\(O(n^3)\)
我们可以更优,使用迪杰斯特拉\(O(nm \space logm)\)
但是我们还关注能否处理负边
所以只有SPFA,Floyd,贝尔曼,Johnson可以解决
原理解释
所以我们解决带负边的全源最短路时同时兼顾时间应该怎么做?
- 使用Dijkstra
但是Dijkstra不能处理有负边的问题,所以我们可以使边变为正数,我们基本得到3个猜想:
- 对每条边进行相同的增量,使所有边非负。
- 改变图的结构,不改变图的性质,使Dijkstra可做。
- 对每条边单独设计增量,使图的性质保证并且全图非负。
可以看出只有第三种是正确的。
为什么第一种不正确?
如上图(箭头错,1->3应该是3->1)3->2的最短路原本是-2(走上面),但是对于边权+5的图(绿)就成了9(走下面),路径发生了改变,不可取。
Johnson算法核心
建一个超级源,到所有点连0 权边,对超级源跑一遍SPFA,求出每个点的dis 值。重构原图边权,对于边
这篇关于Johnson 全源最短路径算法学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南