johnson算法的现实意义

举报
yd_267761811 发表于 2023/06/30 09:43:45 2023/06/30
【摘要】 Johnson算法是一种用于解决边数与节点数之间关系为O(n^2)的带权图的最短路径问题的算法。它是一种结合了Dijkstra算法和Bellman-Ford算法的技术,通过使用一个负权重的环检测器来消除负权重的影响。这种算法的时间复杂度为O(n^2+m log n)。 Johnson算法是一种用于解决多源最短路径问题的算法。它通过将图中的边权转换为虚拟起点的边权来解决问题。 Johnson算...

Johnson算法是一种用于解决边数与节点数之间关系为O(n^2)的带权图的最短路径问题的算法。它是一种结合了Dijkstra算法和Bellman-Ford算法的技术,通过使用一个负权重的环检测器来消除负权重的影响。这种算法的时间复杂度为O(n^2+m log n)。


Johnson算法是一种用于解决多源最短路径问题的算法。它通过将图中的边权转换为虚拟起点的边权来解决问题。


Johnson算法的一个明显缺点是,在边权取负值之后,有负权边的图上不能使用该算法。这是因为负权边会导致最长路径不存在。另外,Johnson算法的时间复杂度为O(n^2 * log(n) + m * log(n)),其中n为顶点数,m为边数。相比于其他多源最短路径算法,Johnson算法的时间复杂度较高。还有一点就是Johnson算法需要先对图做一个Bellman-Ford或者Dijkstra来判断负环,并且需要多次使用堆优化的Dijkstra算法,所以空间复杂度也比较大。


例如,假设有一个图,其中包含5个节点(A、B、C、D、E)和7条边(A-B、B-C、C-D、D-E、A-D、B-E、C-E)。现在,如果要求从A、B、C三个起点到E终点的最短路径,可以使用Johnson算法。


首先,将虚拟起点S加入图中,并将S到A、B、C的边权设为0。然后,使用Bellman-Ford算法求S到其他各点的最短路径。接着,将图中所有边权加上S到该边的两个端点的最短路径长度。最后,使用Dijkstra算法求A、B、C到E的最短路径。


在这个例子中,Johnson算法将会得到A到E、B到E、C到E的最短路径分别为 [A,D,E], [B,E]。












本文转载自:https://www.teamdoc.cn/archives/2937

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。