00:00
各位,我们用图解的方式再给同学们介绍一下弗洛伊的算法的步骤和它的思想。我们打开这准备好的。一个文档来看一下吧,同学们我们以哪个为例呢?我们仍然以前面我们讲的这一个修路或者是公交站的这个图为例,给大家进行讲解,同学们可以看到这是一张图,这个图里面有ABCDEFG7个顶点,他们边的全值也列出来了,这里大家看到啊,那么同学们可以看到,当我们没有做任何处理的时候,它的这一个。初始各个顶点之间的距离表呢,应该是这样子的,这个没有没有疑问吧,同学们你看啊看一下A和A是零,我们代表呢,这记得是零对不对,也就是说这条斜线我们都为零,什么意思呢?我们认为自己跟自己它们相连的距离为零。
01:02
用零来表示,那么A和BAA和A顶点跟B这个顶点呢?它的距离为五,是不是五啊,正确的A和C这个顶点它的距离为七。A和C距离为七也是正确的,A和A和DD这个顶点为NN,我们到时候会用一个。非常大的数来表示,就代表不可直连。对,不可直定,那么同学们可以看到,A和D之间的确不可直接看这条线。A和D之间没有直连的一条线,所以说用N来表示就代表它是不可直连的,其他以此类推,我就不一个个去讲了,所以说同学们可以看到这张图呢,就是我们的一张顶点之间距离的初始化图。那么我们来看。呃,他还有一张图,就是初始顶点前驱关系,我先给大家讲一下这个图代表什么意思,这肯定也是一个数组。
02:05
是一个二维数组,大家可以看得到,也就是说当我们还没有开始去求最短路径的时候,A的A的顶点,A到A的这个顶点就是AA和B之间,他们的前区,就说就说什么意思呢?就是它的前驱也是A,就是自己,是自己吗?因为你现在还没有开始便利,就以自己这个点作为自己的前驱,前驱顶点,那当然在实际的这个过程中,在实际的过程中,这个顶点肯定是在逐渐的变化的。对吧,也也就是说这个会逐渐的跟着我们代码的编写,会逐渐的进行一个调整。因为你在初始化的时候呢,我们认为它的顶点呢,就是A就是自己。就自己好,这个图大家也看懂了,我们再来看下一个。那么这个地方就比较重要了,这个地方就是弗洛伊德,弗洛伊德算法的一个思路和步骤了,他是怎么来玩的呢?同学们注意听哈。
03:11
不着急,咱们一一步一看,同学们看弗洛伊德呢,主要是维护了两张,两张表,或者说两个二维数组,一个是。距离。距离表,一个是顶初始顶点的前驱表,那么假如我们在第一轮循环中,我们要做件什么事情呢?注意听这个有点不好讲,大家认真听啊,就说在进行进行这个循环中,比如说我们以A为例,我们把A当做中间顶点,注意听这句话。我还是用个图,用个用个线来表示,比如说我们以A作为中间顶点,我们把A当做这个中间顶点,那么把A当做一个中间顶点,我们把A。当做中间顶点的所有可能性全部进行一个扫描,再说一遍,把A作为中间顶点的可能性部作为一个便利,然后距离表和全区表的关系就会变成下面的这两张表,我把这个写清楚。
04:16
以A作为顶点,作为中间顶,中间顶点八即,即什么呢?即把A作为中间顶点的所有情况都进行一个便利。就会得到,诶,就会得到新的,或者更新都可以得到新的距离表。和前驱关系和前驱关系。就会得到一个新的距离表和这这个这个所谓新的不是全新的啊,就是更新的意思,就会更新吧,不要写新的,大家容易产生一种误解,就会更新距离表和全局关系,那么当我把A作为中间顶点的所有情况都变离一次过后,它的距离表就变成什么了呢?它就变成了这样一个表。
05:13
和这张一张表说,老师这个题目这下我就听不懂了呀,没关系,我们还是这样子,同学们跟上我的思路,注意听啊,我们尽量让各位同学呢都能够真正的听懂。我把我。我把一个图解Excel表打开,大家看看能不能跟上老师思路捋捋。好,我打开这个图呢,我把弗洛伊德的这一个思路再给大家讲讲,比方说。比比方说刚才老师讲的就是什么情况呢,第一轮毕利OK。我把这个写到这里来。小这里来,我们把它拿过来,大家看一下就行了,好吧,不着急,这是。把A作为中间顶点,所有情况都进行一个便利。
06:01
都进行一个遍历,好,我把这个地方给它设一个纯色图,换成灰色的,然后呢,我们把这个图也拿过来,这个图是不是最最先前的这两张图,呃,最最先前的图是这样子的是吧?同学们来,我把这个也粘过来啊,最先前。是这样一个图,然后呢,它的顶点前区关系图是这样的一个图。我我这样一句话大家就就应该很好理解了,来看一下,也就是说如果我把A作为中间顶点的所有情况都遍利以后,以后呢,这张嗯更新就变成这个样子了,来把这个画一下,就是我们这一个距离表就变成这个了。那待会我再我再讲是怎么实现的啊,不着急,而我们的前顶点前区这张表呢,就变成了。
07:01
这个图它是怎么变的呢?诶同学们,我们来看看他是怎么变的呢?来跟上我的思路,大家首先看一下,我把这个稍微放小一点点,同学们首先跟着我的思路来看一看,先来跟着老师思路想一想,各位同学,如果我们把A作为中间顶点,请问请问有哪几条几条路径?可以把A当成中间顶点,同学们能能想起来吗?来,我写一个文本。注意听啊,注意听他说将。将。将A作为。作为中间顶点的情况的的情况,情况有,比如说第一种,第一种是不是cag可能是真实存在的,就是CA是一种真实有可能存在的A作为中间顶点的。
08:03
对吧,那也就是说有一种是C。A文章写大写CA。G这个大家看出来了吗?我问大家,如果这个CG完了过后,这个距离是不是实际上就是九啊,就是就是相当于说CG这个距离就变成就说C到G,如果以中间作为以A作为中间顶点的话,这个距离就变成了九,这个能理解吗?因为七加二嘛,这是一条线,好,还有一种可能性是cab,这个大家看到没有,就B就是说A作为中间顶点,还有一个是CA,哦不不cab,那么同学们cab它的距离是不是七加五等于12啊。这个大家能看到吗?还有一种可能性是什么?同学们还一种可能性是gab,是不是GA?注意听啊,这个还是有点重要的GA,我问大家,如果在这种情况下,我GA将A作为中间地点,是不是整体它的距离是七啊?
09:10
是不是好三种情况,当然有同学可能说,诶,那不对呀,我们还可以是,还可以是,你这是C。Cag,那我也可以是GAC呀,我们这是无像图,不考虑这个,再说一遍,我们这是无像图,不考虑这个,因为你cag和GA GAC不是一样的吗?我这是无项的,所以说我就考虑一个情况就可以了。明白我的意思了吧?好,同学们看,那如果这样子得到过后,同学们请思考你原先这个距离CCG。你原先这个C到G是不是,原先这个地方是。一个无穷大的呀,或者是一个大值,所以说所以说这个地方就会被更新,为什么会更新呢?因为你原先就说,就说你原先是是一个,嗯,是一个很大的距离,就是我们认为无穷大吧。
10:10
当然其实我们这写的没那么大啊,可能是6535就是一个很大的值,那么这个N呢,肯定是大于九的,所以说我就会把这个N替换成什么呀九。能理解了吧,那么让这个地方一替换,它的C和G是不是也反映成G和C啊,那也就是说你这换了G和C的关系呢,也要换,是不是这个地方也要换啊。因为这个是CG到C和C到G不是一回事吗?因为我是无相的说这个地方也要换成九理解了吧,所以这就体现出这两个点就被替换了理解了,注意听啊,至于它是怎么做到的,待会我再讲,不着急,那紧接着呢,我们再来看cab,好,Cab也实际上就是C到B嘛,那么C到B这是无穷大。哎,你原先是无穷大,好,你无穷大,现在我是12,当然我要替换了,因为我12比你小啊,比你这个N小,所以这个也替换了,所以你看这个地方就造型变成12,同样你CC到B和B到C是一回事啊,那这个地方是不是也应该换成12啊,各位朋友。
11:18
哎,所以说这个地方也变成12了。来,咱们接着玩,咱们接着玩。那有一同学说你就还有啊,对的,G到B,没错,G到BG到B是这,OK,大家看你原先的距离是三,而我经过A作为总点是七,请问七大还是三大?显然是七大呀,所以说我就不能替换它,也就是说人家本本身就一个直连的。大家想想我们刚才的一个算法,是不是也就是说人家G到B本身原先的人家上一次的距离已经是三了,你让A作为这个中间顶点还变成七了,你你是不是应该你替换人家吗?你不能把三变成七啊。
12:03
你变成七不是变大了吗?说这个三就不动,这个三不动,那就意味着呃那个G,嗯,那就意味着B到G也不能动,就B到G这也是三也不能动,所以说其实这就动了四个地方。明白了吧,说这这这个图是怎么推过来的就知道了。就知道了,好的。那么我们再来看它的前驱。大家想。大家想一个道理啊,你刚才把这一个NNNN,这四个N变成12,变成12 12 12,这个是九,这个是九,你是凭什么的呀?就说你你凭什么可以把这个把原先的N变成12,凭什么可以把这个N变成九,是不是就是因为你在这个地方用到了A作为中间顶点来进行过渡啊,所以说就会对于这种情况下,它就会把原先你这个N这对应的这个顶点就是有个对应关系啊,注意看这个N。
13:08
这个B就换成了A,听清楚了换成A,当然同样道理,这个地方是不是也要变成A啊,也就是说你凭什么可以把这个N换成12,就是因为你让A作为中间顶点进行进行的过渡,所以说就把这个前区呢就换了,就好比就好像就好像这种感觉就说C。到B的距离,之所以可以拿到这样这样一个12,是因为你的这个前去变成A了。你可以理解成CC通过了A到B,所以说我们就把这个顶点换成这个A,前驱顶点就变化。明明白了吧,不管是谁的谦虚,反正代表的含义就是说我C到B之所以能变成这个东西,就是因为我中间借借用了这个A。
14:00
这个中间顶点,同样的道理,同样道理,你这个地方变成这个是不是,你看啊这个地方。这个点原先是C,你C通过,也就是C经过自己再到G,它是一个无穷大,不相当于说不能关联,那现在可以了,是因为用了A作为中间顶点,所以把这个地方换成A,同样的道理是不是这有个对应关系,这个地方也要换成AR。所以说当我这样处理完了过后,我得到的一个前驱关系表就变成了这个德行。就这样子的。好,我们请这个,这个图大家应该看懂了,对不对,看懂了,现在来解释一下把A作为中间顶点的所有情况都进行便利,这个是怎么实现的。他怎么就能把A作为中间顶点的所有情况都考虑到呢?各位同学,我们现在讲它的算法的一个地方,它是这样子的啊同学们,那我这个因为要写字,所以说我就把刚才这个就。
15:00
这个图我就不保存了啊,同学们好,我我保存一下吧,因为将来可能会给大家截一个图好吗?OK,这个地方卡在这了,好,我先把这个图像放着啊,我我现在在解释另外一个问题,同学们跟上我的思路。现在我要解释的问题是,就是他怎么就把A作为中间顶点,所有情况能够考虑到呢,它是这样子的,各位朋友,首先呢,我们还是画这么一个东西。首先它它一共有几个顶点,一共有七个顶点,对不对,所以说。所以说我先ADCDFG一共七个顶点,好,我把这个呢当成一个数组,这个当当成中间,注意听中间。中间顶点没问题吧,好,紧接着我再复制一份。我再复制一份,认真听哈,再复制一份,这个呢,我认为是出发顶点。
16:05
哎,出发顶点,出发顶点还是这一份好,我们还有一个那个终点叫终点。终点啊,OK中呃结结束点位,这终点就行啊,终点。终点好,终点其实说白了还是这这一个数组是吧,还是顶点数组,那它怎么玩的呢?它其实是用的一个一个循环,它是这样子的,同学们听我讲哈。他要以A作为中间顶点呢,它从中间顶点先挑出A。假如说这个地方是以K来进行表示的,那现在K只要取零。K只要取零,实际上就取到A这个。K如果取零的话,下边取零的话,是不是就把A这个顶点。挑出来了,然后呢,我再注意听,我再以这一个出发,顶点这地方再选一个选一个,那么这边假设我们叫做I,好吧,I我也从取零。
17:11
然后这个I0的时候呢,我就这样写了,相当于说I等于零,K等于零,我让这个A经过A到达这个A,这是一种好,我们再看第二个。这边相当于说节又等于零。好,现在呢,K和结都不变,我在想现现在接着再再做K。就是说相当于说A经过A,从A点出发,经过A这个顶点到达B,因为我要把它作为中间的所有情况考虑,所以说这个节呢,它是从零到一到二到三到四到五到六。是不是当我这个K等于零,J等于零,而节从零到六进行变化的时候,是不是相当于说我我把这个情况就走完了,相相当于说A从A这个A出发,顶点经过A这个顶点到达终点的七个情况就考虑完了。
18:14
好,当然我每每做一步呢,我会把这个距离求出来,求的过程中我会把最短距离找到。最短距离找到同样道理,我紧接着让这个节又变成一二啊,I变成一,那如果I变成一,是不是此时此刻我就选的是B?也就是说从B点,从B这个顶点作为一个出发地点,再经过A,然后再到。Abcd为中点,就是说现在这个又变成一,变成二,变成三,变成四,变成五变成六。是不是把所有情况都全部考虑了,当然K不要变了,K是不变的,也就是说我在K不变的时候,里面有个双层循环,就可以把我们A作为中间顶点,所有情况全全部便利到,然后每变变离这个过程中呢,在这个负循环变离过程中,我们不停的把这个最小的距离进行一个更新,就是不停的在更新哪个表呢?更新我们的这张表。
19:20
是不是整个一一处理完了过后,我们就把以A为中间顶点的这个最短路径就全部拿到了。你想一想,是不是假设有一个情况,它中间里面是不连的,是不是就变成到一个NN是无穷大,是不是这个N就不去不去替换就完了。那么当我把A作为这个中间顶点做完了过后,我然后把这个循环再让这个K变成一,是不是又把B作为中间顶点,再像这样来一圈?那么就把B作为中间顶点,所有情况又进行编辑,又会更新我们的距离表和前区关系。当我们把这个K又从零到二到三到四到五到六更新完过后,好同学们,我们整个。
20:10
这个最后这张表就是同学们看到的这个距离表,就是。各个顶点到其他顶点的最短路径。也就是说,最后结果是存在。这个距离表的,当然前区关系表也在不停的变化。所以说我们这个弗洛伊的算法,它其实很简单,其实就是三层循环呐。就是三层负循环,三层负,那么每每每循环一次,就是把这个三层负循环结束完了过后其实我们就得到了A,就是每一个顶点到其他顶点的最短路径。就拿到了,所以代码其实特别的简单,就是三层for循环就完事。那最后的结果就是存在这个距离表的。明白这意思吧,但是大家看到这个弗洛伊的算法虽然很简单,也很好理解,但是呢,它的时间复杂度是比较高的,为什么呢?因为它是N的三次方,它是立方,立方阶在前面我们讲过,时间复杂度,立方阶它是。
21:15
变化,呃,这个还是很快的,比如说现在我们有100个100个点,那么你整个这个便利就是100乘100,再乘100。那这个还是很大的,假设我们变成1000,好这个就又又又这样成了,所以说它的时间复杂度还是比较高的,但是呢,理解起来还算是非常easy,还算是非常easy,好,这个图我讲到这,大家大致明白是什么意思了吧。大致明白吧,就是说白了,他就把所有你作为中间顶点情况全部进行便利,在便利过程中,他还在不停的进行这个更新就完事了。当然这个中间顶点呢,你这算出来过是不是你第一次遍历A过后,是不是是不是就是最短的也不一定,因为在后面这个过程有可能给你再再不停的选最小的嘛,可能给你再替换一下都是有可能的,明白我的意思吧,好呃,我的他的这个弗洛伊德的一个算法的思路,我就给大家讲到这里了,大家看理不理解。
22:14
好了,那我把这个图呢,也给大家截到这儿,待会儿我可能要用好吧,好的,这是我们的第二张图。也就是说在这张图里面呢,我给同学们解释了一下,它到底是怎么样把A作为中间点的所有情况就得到了呢?好,当把A做完了过后,再把B,再把C,再把B,再把D。EFG全部都做完好,最后我们的结果就会存在哪张表里面,整个最后这个结果就在这个距离表里面。这个距离表里面这一行就会记录A到A的最短距离,然后这个点就会记录A到B的最短路径,而这个距离呢,就是A到C的最短距离,下面这一点就是A到B的最短距离,A到B的最短距离,那如果看F的话就是。
23:05
看这个点就是。F到A的最短距离,那这个就是F到B的最短距离,我说是最后啊。好,再看这个地方,到时间更新完了过后,这个位置存的就是F到F的最短距离,这个位置就是存的F到G的最短距离,以此类推。其实大家有没有发现弗洛伊的算法,它比我们前面讲的。理解适当的算法,好理解,而且实现大家也看出来其实挺简单的,就是一个三层循环搞定了。只是时间复杂度稍高一点,好,同学们,那关于我们这一个普罗一的算法的,它的一个图解的思路就给同学们讲到这里。
我来说两句