图的最短路径~~~《码农也穿越》第一集

本集简介

我本一介小码农,整日耕于代码中。

一觉醒来竟穿越,略施算法得圣宠。

每日的生活就好像一遍遍for循环,上班,开会,撕逼,加班,摸鱼,加班摸鱼。

好在,最近可以看《赘婿》,把我从千篇一律的生活中拯救出来。

又是一个周日的晚上,看着主人公在古代入赘豪门,广开分铺,结识丞相,不禁感慨我要是能穿越就好了,可是一个程序员穿越回去可以干什么呢?

郁闷之下开了一瓶啤酒,边胡思乱想边追剧,不胜酒力的我就这么迷迷糊糊睡着了。

不知道过了多久,我耳边听见有人在喊:”大人大人,皇上有急事招您!”

我惊醒一看,周围已不是我出租屋的装饰,而且立着汉白玉的柱子,四周的墙壁也全是白色石砖雕砌而成。

我一把拿过床边的镜子,镜子中的人留着长发,貌比潘安,散发着一股年少有为不自卑的气质,一扫往日一副郁郁不得志状态。

我竟然真的穿越了!

为了保证穿越之后的仪式感,我还是打了自己两巴掌,没有问题!

门外的仆人越发着急,我忙说起来了起来了,心想我都位高权重了咋刚起床就得上班。

仆人直接进来帮我换好衣服,并说高公公在外面等候多时了。

在高公公的带领之下,我们坐上马车直奔皇宫。

担心言多必失,我全程不发一言。但是依然按捺不住我激动的心情,这次投胎我给自己打个满分。

很快到了皇宫,高公公带着我一路小跑,直奔皇上书房。

行过电视剧看过的大礼之后,皇上满脸愁容,叹气道;”爱卿啊,贵妃整日郁郁寡欢,问起原因,是因为思念家乡的荔枝了,可蜀中到长安数千里,中间涉及了几百条官道,途经几百个驿站,绕来绕去,送到时荔枝都已腐烂。爱卿可有什么法子,来找出蜀中到长安的最近道路啊。”

我一听,这不是我的老本行吗,无向图的最短路径啊!

我当时恨不得表演一下宣纸毛笔写算法的祖传手艺,可一寻思,皇帝也看不懂代码,搞不好以为我在鬼画符。

算了,能和皇帝讲清楚就行了。

于是我上前一步:”臣有一计,按此计可寻得最短路径,定可让贵妃吃上鲜美荔枝。”

皇上大喜:”笔墨伺候,让爱卿给朕道来。”

我在纸上画到

皇上请看,我们可以类比于从0点到4点的最短距离。

算法很简单,用三个变量,重复走三步,即可得到最终结果。

三个变量

  1. sptSet (shortest path tree set) 数组

创建一个数组sptSet,用来记录最短路径中包含的顶点,也就是哪个顶点计算出来到源点的最近距离了,就把它加进去。

最初,此集合为空。

  1. distance数组

创建一个数组记录每个顶点到源点的距离,当然最开始为INFINITE(无限大)。

同时将源顶点的距离值指定为0。

  1. parent数组

这个是当我们更新distance数组的时候,记录该节点的上一个节点,好记录整个最短路径所通过的节点。

三步走

  1. 选出一个不在sptSet数组并且distance数组中之最小的节点,该节点我们可以称之为u
    当然,第一次就是选择源节点0

  2. u放到sptSet数组中。

  3. 遍历u所有相邻的顶点,如果相邻顶点i的距离值(即distance[i]的值)大于u的距离值加上u到该相邻顶点的距离之和S,我们更新相邻顶点的距离值为S
    同时,修改parent数组,即parent[i]=u

如此重复下去,直到我们遍历完全部节点,就可以获取源点到每一个节点的最短路径。

当然,从蜀中到长安的最短路径也知晓了。”

皇上一脸茫然的看着我,我才意识到,我已经穿越了,这样讲皇上肯定听不懂,就是看这个文章的现代人都不一定能懂。

不如一步步推导,皇上肯定更加清晰。

我又说道:”皇上,来我们实际走一遍,您便一目了然。”

数组
sptSet最初为空,distance{0,INF,INF,INF,INF,INF,INF,INF},其中INF表示无穷大。 现在选择距离最小的顶点,也就是选择顶点0,将其包含在sptSet中。

因此,sptSet变为{0}。 将0包含到sptSet之后(图中变绿节点),更新其相邻顶点的距离值。

0的相邻顶点是1717的距离值更新为4和8。

同时修改parent数组

parent[1] = 0
parent[7]=0

选择当前具有最小距离值且尚未包含在sptSet中的顶点,这次选择了顶点1并将其添加到sptSet。 因此,sptSet现在变为{0,1}。

更新相邻顶点的距离值,因此顶点2的距离值变为12。

同时修改

parent[2]=1

依然选择具有最小距离值且尚未包含在sptSet中的顶点,这次选择了顶点7。 因此,sptSet现在变为{0,1,7}。 更新顶点7相邻节点的距离值,即修改顶点68的距离值为15和9。

同时修改

parent[6]=7
parent[8]=7

我们如此重复,直到遍历全部节点。

皇上,我给您写个代码,您立马就知道怎么回事了!”。

此时皇帝更加迷惑了,赶紧摇了摇头,说:”爱卿,你就说需要多少学士,计算多久能出结果吧。”

我恍惚间觉得自己好像在被产品催问什么时候能上线,立马答道,只需十名学士,三日必可出结果。

皇上顿时开龙心大悦,许诺此事若成必重重封赏,我一想到刚穿越就能立功,三跪九拜退出书房。

数日之后,我已算得从蜀中到长安的最短路径,鲜美荔枝也一担担运往皇宫之中。

一日无事,我站在宫外高楼之上看着骑士背着荔枝驰入皇宫,不仅感叹自己之前虽是码农,在社会上地位不如医生老师之辈,穿越之后竟也能如鱼得水,活得如此滋润。

此时突然听到旁边一位老先生叹气到: 皇上荒淫无度,百姓民不聊生,这日子何时是个头啊。

我凑过去,问道:”老先生,可有心事?”

老先生摇了摇头,转身在纸上作诗一首:

长安回望绣成堆,山顶千门次第开。

一骑红尘妃子笑,无人知是荔枝来。

写罢便拂袖而去。

望着老先生远去的身影,我突然意识到,自己也要做点什么,来改变这个朝代了。

未完待续。。。。。。

友情提示,关注公众号可提前观看下一集哦!

创过业,赔过钱。遂转行,程序员。

从外包,到大厂。写代码,写文章。

胡思乱想,文章沙雕。

欢迎关注,与君同好。

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

JVM笔记--如果你写JVM,最需要考虑的重要结构是什么?

2021-3-16 10:44:00

经验教程

高精地图技术专栏 | 基于空间连续性的异常3D点云修复技术

2021-3-16 11:20:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索