文档章节

Johnson算法:多源最短路算法

o
 osc_g8254g7s
发布于 2019/08/19 18:54
字数 520
阅读 47
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

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]$,无论路径如何变更,都不影响这个常量的存在,所以原来的最短路依然保留

(当然我的证明含糊如放屁)

所以我们可以直接用这个算法解决一些特殊的问题

o
粉丝 0
博文 499
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
硬实时操作系统--Raw OS

Raw-OS 起飞于2012年,Raw-OS志在制作中国人自己的最优秀硬实时操作系统。 Raw-OS 操作系统特性 内核最大关中断时间无限接近0us, s3c2440系统最大关中断时间实测0.8us。 支持idle任务级别的事...

jorya_txj
2013/03/19
6.3K
1
阿里云开放存储服务的C语言SDK--OSSC

OSSC(Aliyun Open Storage Service C SDK)为阿里云开放存储服务(OSS)提供了一套完整易用的C SDK。 OSSC完全采用C语言开发,并实现了类似面向对象的调用方式,遵循了良好的编码规范,目前O...

大卷卷
2012/10/22
4.6K
0
可视化的蛋白质配位图--VPLG

可视化的蛋白质配位图(VPLG)使用一个基于图的模型来描述蛋白质的结构,基于超级二级结构级别。一个蛋白质配位图是计算从原子坐标在PDB文件和二级结构作业的DSSP算法。在这个图,顶点代表二级结...

匿名
2012/10/28
2.2K
0
C++科学计算库--O2scl

一个面向对象的 C++科学计算库,可用于解方程,最小化,微分,积分,插值,优化,逼近,分析,拟合等。许多类可操作于通用的函数和向量类型。可用于O2scl在Linux,Mac和Windows(Cygwin的)平...

匿名
2012/10/29
4.7K
0
中州韵输入法引擎--rimeime

Rime全名是「中州韵输入法引擎」,它不仅仅是一个输入法,而是一个输入法算法框架。Rime的基础架构十分精良,一套算法支持了拼音、双拼、注音、五笔、仓颉等所有音码和形码输入法,远比基于码...

tsl0922
2012/11/13
6.3K
2

没有更多内容

加载失败,请刷新页面

加载更多

处理“ java.lang.OutOfMemoryError:PermGen空间”错误

问题: Recently I ran into this error in my web application: 最近,我在Web应用程序中遇到此错误: java.lang.OutOfMemoryError: PermGen space java.lang.OutOfMemoryError:PermGen空间......

技术盛宴
48分钟前
7
0
从JS数组中删除重复的值[duplicate] - Remove duplicate values from JS array [duplicate]

问题: This question already has answers here : 这个问题已经在这里有了答案 : Get all unique values in a JavaScript array (remove duplicates) (79 answers) 获取JavaScript数组中的......

法国红酒甜
今天
11
0
如何使用AngularJS在浏览器的控制台中访问$ scope变量?

问题: I would like to access my $scope variable in Chrome's JavaScript console. 我想在Chrome的JavaScript控制台中访问$scope变量。 How do I do that? 我怎么做? I can neither see ......

fyin1314
今天
18
0
ImageMagick - 添加水印

背景 最近制作思维导图想添加自己的水印,网上很多例子都是使用ImageMagick来完成。但是不少代码在本地并不可行。经过一番试验,找到两个方法。 方法一 代码 stackoverflow方法改良: conver...

wffger
今天
11
0
OSChina 周四乱弹 —— 到底是怎样的饕餮盛宴在等待着我!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑推荐 :《你 能 來 保 護 我 的 世 界 嘛》- 歪门 《你 能 來 保 護 我 的 世 界 嘛》- 歪门 手机党少年们想听歌,请使劲儿戳(这里)...

小小编辑
今天
79
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部