如何理解最短路径中的 "松弛 "操作
这是图算法的第五篇文章:图解:最短路径之如何理解“松弛”or“放松”?
最短路径问题的目的是找到从一个顶点到达另一个顶点的成本最小的路径。最短路径算法
被广泛地应用于解决各种复杂的问题,比如在地图中寻找两个地点之间的最短路径,如何在网络连接中为路由器寻找最短的传输路径等等。为了实现最短路径算法
,人们发明了一系列的算法,比如:Dijkstra算法
与Bellman-Ford算法
。但是这些算法都基于一个被称为放松的基本操作
relaxtion,有些人称为松弛,我就直接简单翻译为放松了,别管怎么叫,理解就行
在这篇文章中,我会详细介绍放松操作,同时给出解决最短路径问题的基本(通用)思想。
这篇文章的大纲是:
- 1.什么是最短路径问题?
- 2.怎样理解边的放松?
- 3.边的放松顺序重要吗?
- 4.无环加权图的最短路径算法
1.什么是最短路径问题?
我们接下来要讨论的问题被称为单源最短路(Single-Source Shortest Path),通俗来讲,就是给定一幅加权图和一个特定的顶点s
,称为源
;我们的目标是对于图中任意一点v
,计算从源s
到达v
的最短路径
G=(V,E)是一个加权图
- 图G中的边有权重
- 可以为有向或者无向
- 可以是连通的或者不连通的
- 取
s
作为一个特殊的顶点——叫做源
目标:对于图中任意一点v
,计算从源s
到达v
的最短路径
我们一起来看一个例子:
在这幅图中,我们取源s
,对于顶点A
,从s
到达A
的路径只有一条SA,所以最短路径就是SA
,最小权重为1
;对于顶点B
,从s
到达B
的路径有两条:SB
与SAB
,显然最短路径是SAB
,最小权重为1+1=2
。
对于下面这幅图呢?
我们把最小权重写在每个顶点内部会得到图二,这就是我们的目标!
2.怎样理解边的放松?
现在,我们就来一起看一下放松这一个最基本最重要的操作吧!
对于一条从顶点u
指向顶点v
的边u-->v
来说,如果满足 d[u]+w(u,v)<d[v],就更新d[v]
,使得d[v]=d[u]+w(u,v)
;这就是对边uv
的一次放松操作;
其中,w(u,v)表示边的权重,d(u)表示顶点u到达源s的最短距离(目前已知)
以下图为例,通过这次放松,我们有可能能够改进d[v]
!顶点 v
原本有一个最短路径值d[v]
,它是在我们没有掌握足够多的信息的情况下做出的临时判断,d[v]
可能真的是最终的答案也可能不是。我们就是通过对边uv
进行放松操作来看一下能不能改进。如果d[u]+w(u,v)<d[v]
成立,也就意味着我们找到了一条更近的路径到达顶点v
,这条路径是通过顶点u
的那条。所以,我们就更新顶点v
储存的值d[v]
,同时还要更新路径信息,使得edgeTo[v]=u
上面就是放松的定义,它的实质就是判断一个顶点能不能有更好的选择,已知的最短路径能不能更短;如果满足那个不等式,就说明我们可以找到一条更好的路径,就更新它,改进它!
上面我们谈到的是对边的放松,但是在实际的代码实现中,我们的操作是对一个顶点进行放松。这儿理解起来很自然,对一个顶点进行放松就是对所有从该顶点发出的边进行放松的总和
在上图中,我们对顶点v
操作中,对它相邻的三个边进行放松,其实质就是在问相应边对面的顶点————“你能够被改进(更短)吗?”
在了解了放松这个操作之后,我们就来看一下如何利用放松来求最短路径,下文以一个很简单的图来举例
我们首先将所有的顶点的值d[v]
标记为无穷大(因为我们还不能到达这些顶点),源s
特殊处理标记为0
,即d[s]=0
,因为源s距离自身的距离显然为0
接下来,我们对顶点s
进行放松。也就是对每一个从顶点s
发出去的边进行放松,分别是SA
与SB
。先对SA
放松,因为d[s]+1<∞
,符合放松的条件,放松边SA
同时使edgeTo[a]=s
,得到图二
然后对边SB
放松,同样因为d[s]+1<∞
,符合放松的条件,放松边SB
,同时使edgeTo[b]=s
得到图三
很容易发现,图三并不是最终的答案:SAB
边要比SB
边短,然后,对顶点A
进行相同的放松操作,得到图四即为最终的最短路径,同时改变edgeTo[b]=a
。
图五就是操作的全部流程:
最后,我们可以通过edgeTo[]数组
来得到所有的最短路径。比如根据edgeTo[b]=a
得到顶点B
是从顶点A
过来的;而再根据edgeTo[a]=s
得到顶点A
是从顶点S
处过来的,由此溯源了一条从S
到达B
的完整路径!
3.边的放松顺序重要吗?
在上面的篇幅我们讨论了使用放松操作获得最短路径的一个简单示例,我们从前往后依次对顶点S和A进行放松。但是由于我们的示例实在是太简单了,就没有重视放松的顺序!在这里,我想说的是,对于一个比较大的图(至少顶点不再是简简单单的三个),边的放松顺序重要吗?或者说不同的放松顺序能够达到相同的目的(求最短路径)吗?答案是否定的!
我们还是以一个例子说明这件事情:顺序很重要!
在图中,如果你先放松顶点S
,再放松B
,C
最后放松顶点A
就会出现问题!你会发现,当放松完顶点B
后,d[c]=5
,最后对A
放松并不会影响d[c]=5
的事实;所以,最后我们得到到达C
的最短路径的值为5
,然后实际上并不是这样,从图中不难看出,最小值是SABC
,为4
!
或许从听到我这个问题你就感觉到顺序是有要求的,现在更加证实了你的想法,记住:放松的顺序很重要!
我们随后要讨论的好几种最短路径算法,都是在研究
放松的顺序!比如:
Dijkstra算法
如何决定边的放松顺序主要取决于图的性质
【有环无环】【有无负权重边】
接下来我们就以无环加权图为例来看一下具体的实现过程。
4.无环加权图中的最短路径算法
算法:先对图进行拓扑排序,然后按照拓扑顺序放松顶点
我感觉伪代码更能体现思路,所以在下面给出了伪代码,具体的代码实现可以看一下算法4
:
DAG-Shortest-Path(G, s)
Topological Sort G ;
For each v, set d(v) = 1 ; Set d(s) = 0 ;
for (k = 1 to |V|) {
v = kth vertex in topological order ;
Relax all outgoing edges of v ;
}
return d ;
首先对原图进行拓扑排序,得到顶点的拓扑顺序,见【图一】
然后,将源顶点的距离初始化为0
,其他顶点的距离值初始化为∞
,从左向右依次对每个顶点放松
至此,按照拓扑顺序放松了所有顶点,最短路径也就求出来了。注意:该算法有两个比较重要的性质:
- 1.能够处理负权重的边
- 能够求出最长的路径(只需要将原图的所有权重取反即可)
参考:Understanding Edge Relaxation for Dijkstra’s Algorithm and Bellman-Ford Algorithm
5.后记
码字绘图不易,如果觉得本文对你有帮助,还请不要白嫖,关注、点赞、都是对小超创作的一种认可!比较做任何事情都需要反馈~
推荐阅读
-
如何理解最短路径中的 "松弛 "操作
-
刘韧工作手册(2023年版)-17 共同学习,共同进步,搭建共识。一起工作的基础,是对彼此能力的认可,继续一起工作的基础,是能力的共同提高。共同进步的基础,就是共同学习,共同学习的基础,是看过同样的书。 年轻时,男女谈恋爱,双方世界观趋同,差距不大。后来,世界观逐渐拉大,对话成了鸡同鸭讲,我讲,你听不懂。你讲,我不感兴趣,甚至闹离婚,双方自然而然走不下去了。工作也一样,同事间如果差距越来越大,最终,无法一起工作。 我为了和别人搭建共识,会处心积虑向其推荐读书。听什么歌,观什么电影,看什么书,能在一定程度了解一个人。 有人说,金庸的书是文学。我说,那是娱乐。文学是“真、善、美”,首先是要“真”,就是情感真实。而在金庸的小说里,类似“九阴真经”、“葵花宝典”的秘籍是假的,小说里的人物寻得秘籍,一夜之间就能武功猛增……这样的情节,在现实中可能吗?生活中,漂亮的富家女黄蓉会爱上傻小子郭靖吗?金庸看多了,人会追求走捷径,工作生活“走捷径”会害死自己。 18 礼物,是人际交往中的情感润滑剂。互相送礼物,增进感情。不知道买什么,就买吃的。 英国人做客,会送主人红酒、鲜花和小卡片,回家后,会写感谢信。在新加坡,朋友们来家,常带些做好的熟食,大家一起吃。 2000年,我听说谷歌在办公室给员工备吃的。当时不太理解,后来才知道,“在一起吃”这个行为,有助于消除紧张和敌意,人更容易感到温暖和轻松,更愿意敞开心扉,是社交中增进感情的好方式之一。脸书新加坡总部,午餐,公司会请高级厨师做六种风格的菜,每一道菜都做的极好,甚至比五星级酒店的饭菜都好吃。他们的员工告诉我,根本不想回家,就想在公司吃饭。 19 坦诚,不装懂,打破沙锅问到底。想当然半天,不如简单试一下。要学会积攒各种低成本测试方法,并勤快地去试。超大额跨国汇款,先汇1元,测试路径是否畅通。没有招,没有策略库,一筹莫展。 有句古话,叫“以其昏昏,使人昭昭”。很多人对“学而优则仕”这句话的理解,是典型的“以其昏昏,使人昭昭”。这句话常被人解释为“学习好了就去当官”,若照此解释,下一句“仕而优则学”只能解释为“当官当好了就去学习”!这显然说不通。这里的“优”,不是“优秀”,而是“空闲”的意思。很多人不清楚,却到处教人解释这句话。 《水浒传》是中国版的黑帮小说,讲的是厚黑学,没有道德底线。梁山人为了拉扈三娘入伙,杀光了她全家,把原本是千金小姐,花容月貌的扈三娘指婚丑陋的王英。直到今天,《水浒传》常被解释为“侠义”。 在群里,遇到信口雌黄国学的人,我会问他们,论语中,第一句话“学而时习之不亦说乎”中的“习”是什么意思?很多人解释为“复习”。其实,繁体字中,“习”的写法是“習”,下面一个“白”,上面一个“羽”,指的是“雏鸟学飞”。意思是,雏鸟利用老鸟教的技巧,终于飞起来了。因此,“习”的本意是指老师手把手把心得教给你,让你学会了,有了收获和进步,绝不是指反复“复习”和“练习”的意思。 维特根斯坦说:“凡是可说的就要说清楚,凡是不可说的就该保持沉默。”别不懂装懂。 20 善待帮助你的人。一个人能否成功,要看有没有人愿意帮你。有多大成功,要看有多少人愿意帮你。 别人发现你出错了,提醒你,这些都是你所能得到的“举手之劳”的帮助,你知道了,能改掉,你容易成长。 如何做一个有很多人愿意帮你的人呢? 首先,滴水之恩,当涌泉相报。每次收到礼物,我一定会表示感谢。 其次,得到帮助,一定要反馈。很多帮助不一定非得要你用物质来交换,可能仅仅是你要领情。我会记录所有受到的帮助,并广而告之。我写书时,会把帮助我的人都列举出来,这样做成本不高,但被提到的人会感动。 你们可以回忆一下,有多少人帮过你?如果脱口说出的人数越多,说明你离成功越近。要是发现世界上,愿意帮你的人只有父母,那就要反思了。(完) 刘韧商业写作通识
-
如何详细理解和操作Spring Boot中的Logback日志框架配置指南
-
入门讲解:Spring源代码探索系列" 1. Spring源码剖析导论 2. Spring容器基础操作实战 3. Spring核心容器组件详解 4. 详解Spring基础:XmlBeanFactory源码解析 5. 掌握关键技术:如何获取并处理Document 6. 精读细节:BeanDefinitions的解析与注册过程 7. 深度解析:bean标签在源码中的执行与注册路径
-
南邮OJ Web任务大揭秘:层层挑战剖析 1. 挑战一:迷宫般的目录探索 题目作者似乎穷举了所有可能的目录组合,最终在404.php中的