00:00
各位,我们把弗洛伊德算法的代码给大家实现一下,我们前面已经把准备工作做好了,对吧,只差哪一哪一块呢,就是。我们弗洛伊德算法的核心。用一下就行,刚才我们其实已经把他这个思路已经做了分析,其实说白了就是把每个顶点作为出发点点进行一个便利。然后在便利的过程中呢,不停的去更新距离表和前区关系这个表,最后在距离表里面留下的结果就是我们最重要的结果。好的,那我们来写一下这个代码。写一下,现在这基本完成,就是弗洛伊德算法。我们先把方法写一下,各位朋友,Public void。Fluid。这样写吧。没错,就这样写。呃,刚才我们已经讲过,首先呢,我们要定一个认识,这个是记录什么呢?这个变量变量保存。
01:08
保存距离的,保存这个距离。OK。我我们讲过哈,就是。我们在前面讲的时候,是不是第一层是中间定点,第二层是出发定点,第三层是最里面这一层呢?我们作为作为它的一个结束定点,好,那现在呢,我们就来开始写这三层,For循环for,我先写一下,待会再加注释,那么这个中间顶点我们用K来表示,0K小于什么呢?各位同学,既然是便利嘛,你肯定是不是都要走一下了。是不是就diss我们的N没问题吧?K加加代码,OK,我这写个注释。写个注释好吧,一边写名,这就代表什么呢?呃,代表是我想想应该怎么写哈,中间一点吧,从。
02:01
中间顶点,中间顶点。便利,中间顶点的便利。这样写对中间,对中间顶点的便利。那么K就是下标,K就是中间,中间顶点的下标,这个能理解对吧?负循环紧接着应该是哪一层,同学们是不是就是我们这一个。这个这个出发顶点,而出发顶点说的再具体一点,就是我们在前面讲过的VI。KK是我们的中间地点,你看同学们看VI是我们出发顶点,然后呢,K是我们的中间顶点,而到达是截这个顶点,是不是其实现在就要把这段代码。这个语言用我们代码来实现,明白这意思吧,那我来开始写了。对,那破循环我们先写的是哪一块呢?OKI等于零没问题吧,Ii小于。
03:05
I小于什么呢?也是Dis点很好理解,因为它是便利嘛。那这我再写个注释。没问题了,同学们,我写一段什么注释呢?我说这个是从I顶点开始出发。出发,那出发的时候,其实这边它也仍然是我们的AB,它有这样一个顺序。C哦,那我这复制过来先省点事好吧。也就是你中间顶点呢,会把ABCDEFG走一遍。而。写到这里来。而我们的这个从I顶点出发呢,也会从这走一遍,是这意思吧,同学们,我们在前面已经讲过这事了。好,那走到这里面过后呢,我们是不是还要遍历一下for循环氨T节。节,就是我们到达了一个顶点。
04:00
啊,就是通过K从I从I顶点出发,通过K到达节。对,节就是我们的这次,是这次的一个终点,明白那节小于什么呢?各位朋友节小于DS点认识。这跟刚才我们分析的思路一样。好,拿到。那现在呢,是不是我们要把这个距离算一下呀。好,现在呢,我们把这个N距离算出来,距离就是这段距离,同学们看哪一段距离呢?就是我们这文字所说的。这个这个距离先算出来,就是LK和KG这个距离算出来,那这个这个离怎么算呢?非常的简单哈,这样写就可以了,怎么写第十。是不是IK?加上历史什么K婕。大家有没有发现这个公式还是很形象的,看,先计算出I到K的距离。再得到K。
05:00
到截的距离,那整个这个距离实际上是不是就相当于是挨到,就是相当于这求出什么呢?就是求出。求出从I顶点出发,出发经过经过诶这写错了啊,经过哪个呢?K这个中间顶点。中间顶点到达,到达哪个呢?截这个顶点的距离是这样的吗?同学们,没问题吧,其实挺好理解,因为看I kk在最后,K又在放进前面了,K结好,如果把K去掉的话,你看是不是I结呀。好,那这个拿到以后是不是要做比较啊,如果说你这个认识。因为我上来写的是零嘛,那零肯定是最小的了,如果我这个认识还小于你第四。D是你现在算出来的。呃,这个实际的IK。埃及。
06:00
也也就是说,也就是说我这帮经过这个K顶点,呃嗯,以I顶点出发,经过K顶点到达结,我算出来这个任子小于你直连的这个距离。我就我就重置这个位置的值,如果我不小于你,那当然我就用我这这这个距离作为最小值,明白吧,因为有可能你这个I级它是不不连通的,那就是一个最大值嘛。如果我小于你,我就听完,如果不小于零,我就保存这个字,好我写一下这个地方啊,就是说如果写到这。如果认识。如果认识小于,小于什么呢?DI截这个直连的距离。这个实际上是直连距离对吧,直点距离我就不写了,小于这个距离,那么我就更新什么呢?更新这个值怎么更新就是地势,注意听啊,就是现在我要把I。I什么呢?I及换成这个真正的,那就更新。
07:03
更新距离。这个大家能理解吧,说白了就是I到节,它真实的最短距离呢,就是一个嫩。如果我我这个能大于零呢,那我就不动。我就不动,明白吧,就说我这个能小于你,我再去更新,如果我这个能还大于你,那我就不要去动了。这个点大家应该很好理解,你现在更新距离完了之后,是不是还要更新一下,我们这个前去定点,前去定应该怎么更新呢?Pray这个表。I节它应该换成什么呀?是不是就换成你现在这个中间顶点呢?你的中间顶点是哪一个呀?同学们是不是。介入,大家注意看哦K。是不是啊同学们,哎,这就更新更新前区。前驱。OK,前驱顶点。OK,完事了,就是说你现在这个距离换了就要把对应现在经过这个顶点才能找到的这个位置改改一下,就好像刚才我们分析的。
08:09
比如说诶这不好意思,比如说比如说你现在把这个12这个替换了,那么你也要把刚才到这个情况把把这个这个位置距离表对应的这这个元素的位置也改成现在这个顶点,而这个顶点。这个顶点就是这一次循环里面的K节这个顶点。这个大家应该很好理解,对不对,好,这就更新前驱顶点,那么更新前去一点,这这个地方大家可以看到一共是三层循环就做完了。这个代码就写完了,已经就说我们只需要这么去做一把就行。好。同样,这写出。再写一个注释。在这里面写一个啊,这个节是干什么呢,到达。到达。到达哪个呢?解这个顶点。
09:02
OK,到达结这个顶点,它经过什么呢?就是相当于说是经过了。就是就就写到这儿就行了啊。这个大家应该很好理解的,不难。把这个。写到这,大家来看一下这个这段代码跟我们刚才分析的是不是非常的相似,大家看我们来捋一捋这个思路,假设K等于零,好,这个这上面这个I,哎,这个A就定下来了,然后呢。加,加进来就进来,过后这个I等于零,I等于零是不是先取出这个值,然后它在这里面对结进行一个便利,那就相当于说我怎么求的呢?是。以A出发,经过A到达A的距离是什么?求这个最小值,把它记录到个呢,看看看你这个得到这个认识有没有跟原先这个D时I截的关系是什么样子,如果小于就更新,同样再以再以哪个触发呢?还以我们这个节,这个节没有变化,然后再。
10:03
这个地方在相对于说从A出发。呃,从A出发到经过A到达来地呢,到达B。到达C,到达D,到达E,到达F到达E,是不是相当于这样遍历一次,遍历完了过后,变历完了后,下次该干什么?同学们想一想,是不是下一次我让这个I。变成一变成一,是不是这次就从这个B出发了。还是这样子的,从B出发,经过A。经过A,从B出发,经以中A为中间地点,再去到我们的A,再去到我们的B,再去到我们的C,再去到我们D,再去到我们E,再去到E到F,好,这样其实就把A作为中间顶点,所有情况全部便利了,那便利完了过后呢,根据这个实际情况就更新这个距离就完事了。当我们把A当我把当我们把里面这个六乘六的循环做完了以后呢,把这个K再加一,就把这个变成B,变成B,又像刚才便利呃,把A作为中间顶点那样再来一次,所以它整个这个循环次数应该是六啊不,我一共有七个景点啊,刚才说错了,七乘以七,那就是七乘以七,再乘以七,一共这么多次循环。
11:20
对,所以它是个立方阶的复杂度。好,代码就说完了,我们来用一下吧,看看结果跟我们想的是否一样,来玩一把。好,我在这里面呢,来调用我们的弗洛伊德,弗洛伊德算法。OK grow up。怎么写呢?Loyd完事了,我们运行一把,同学们看效果。他们运行完了过后,我们看这个距离跟我们想的是不是一样啊。好,同学们可以看到这个距离呢,已经出来了,我们想的应该像A到A,我们可能要可能要找找找一个来验一下。好,先把这个结果拿到这儿吧。那这我们来稍微的验一下。
12:00
看看跟我们想的这个算出来结果跟我们实际的结果是否一致。好,我把这个地方,嗯,换一个颜色,好吧,换一个颜色我们验一下。好。呃,怎么怎么验证呢。这样子我们就找其中的其中的几个验一下就可以,好吧,把这个图拿到这边来,我们来验一下。嗯,把这个置顶吧。好,我们来看一看,把这个置顶啊,已经置顶了,我们来看一看,比如说我们看我们以A这个顶点来看啊,以A顶点来验证A到其他顶点的最短距离是不是对的,A为出发顶点。A到A自己肯定是零,这个是正确的,没没问题吧,A到A最短距离可能零嘛,你自己到自己肯定零,A到B呢,A到B它就有直连的线。可以这样走,也可以这样走,但是都是五。啊都是五,所以说它这个距离下来是五也是正确的,A到CA到CA有一条线是这样走的。
13:01
啊,当然你如果要这样走就就就更远了,所以说它七也是正确的,再看到DA到DA的话是这。好,这就线路就比较多了,看到没有可以经过B到这儿,就是十四十四。显然这14你看他没有入选,那么经过哪个呢?比如说经过这个地方看啊,先走这到G,到了G过后呢,再走F,再到这这个算出来12应该这条线是最短的,如果你从这走看啊。就更长了,就是五二加三加五,这就14,所以说它这个距离也是算的是对的,A到EA到E呢,有两条线可以走,显然。那从A走,再到G,再到E,这个一共是六六也是正确的。FA到FA到这个点呢,应该是线路就更多了,那从这看来说,应该这条线是最短的八。正确的A到GA到GG在哪里呢?G在这,那当然这就就是一条线了,就这条线二。
14:01
好,答案是正确的,那其他的每个点我就不一个去验了,好吧,肯定都是对的,大家大家去验一下就行了,如果有兴趣自己去验证,好的同学们,那关于我们这个弗洛伊的算法呢,我们通过验证应该是没有任何错误。应该是没错,思路也很简单,大家会发现弗洛伊的算法其实是比较比较容易理解的。容易理解。容易理解,而且呢,也容易编写,而且容易。容易实现。说这个这个算法还是特别有意思的,所以说人家发现这个算法确实是很有本事的,你看这个东西你怎么能想不到呢,你看弗洛伊德这个人,人家。在七几年就想到这个算法,说你这个算法关键是他能想的到那去,他诶他发现通过这样一个循环,不停的以某个点作为中间理念,不停的去更新他的。嗯,距离和前距一点诶就可以搞定啊,特别有意思啊,特别有意思,好同学们,那关于弗洛伊的算法呢,就先给同学们讲到这里,我们把嗯,弗洛伊德讲了什么内容做一个小结来看一下。
15:11
捋一捋我们的思路,好,打开我们的笔记,对,打开我们笔记,我们把思路捋一捋。那么关于弗洛伊德算法我们是怎么讲的呢?来聊聊。来往下看一看,我们是整理一下这个代码。和笔记好吧。稍微有点慢,往下拉一下。上次呢,我们已经整理到迪杰斯特拉了,现在我们看弗洛伊德,弗洛伊德我们是怎么讲的呢?来聊聊这个话题,首先呢。诶,首先我们先给大家介绍了一下弗洛伊德算法是什么,对不对?他和狄杰斯特拉算法区别又是什么,在第四点也做了一个阐述。好,我在这儿来。写哪些?没问题吧,好在这儿。符号一的算法。我们先对弗洛伊的算法呢做了基本的介绍。
16:04
是吧?做了基本的介绍。然后说了四点。这个很很好理解,就说完了,把弗洛伊的算法说完了后呢,我们来说一下它的基本思想,基本思想先是用文字描述了一下,不太容易理解,所以说接着用图解的方式再说一遍,是这样子的吧,同学们好把技能也拿过来。这个地方我们说的是弗洛伊德算法的他的一种思想。好,这边有三点。那关于图解的方式呢?我把这个图给大家拿过来好吧。嗯,总体来说这个图它是。怎么来分析的呢?我这里有这个东西,我这次就拖过来复制过来。这是我们对它的一个图解分析。好,放到这儿。把这过后呢,我们把格式也带过来,另外是不是我们自己画了,我们自己也画了两张图,把这两张图呢,也拿过来好吧。
17:07
有点卡稍等一下。我们是在讲解过程中截了两张图,我把这两张图呢,也给同学们板书到我们的笔记中去就可以了。诶,这怎么卡了,在这第一张图是这个。是不是我们分析了一下,诶,它是怎么怎么回事,把A作为中间顶点,其实有效的顶点就有效的就这么就这么三种,其他的你是不是直连的,那那更不靠谱了,因为你如果不是直连的话,它的距离是大写的N嘛,那更不能去进行这个更改了。好,这是我们。自己画图分析的一个流程,这是一张图,给大家截到这来。是不是还有一张图啊,还有一张图,这张图呢,我们也拉过来。啊,就这张图,这张图呢,我给同学们讲到这里一个关键点就是怎么样把一个。
18:00
点作为中间顶点进行进行一个遍利,就是要把要把那个A作为中间顶点,所有的情况都进行遍历,我们其实这里面用的是一个三层循环,那么对于一个顶点来说,其实就是一个双层循环就可以了,就是。嵌套循环如果对于所有的点,那就是三层循环。对不对,K不动,K假设为零,然后让埃及。在里面进行一个双层循环。这样就可以把K等于零的这个顶点的所有作为中中间顶点的所有情况全部编辑到,而且不停的根据实际情况更新它的这个距离表和前区关系表。好,这是我们画的这张图。没问题吧?这是图,那这个图完了过后呢,是不是,诶这个图有点不清晰。把这个思路讲完了过后,我们就用代码把这道题做了一个实现,是这样子吧,同学们好的。我把这个也给大家阐述一下,非常简单啊,非常简单,来捋一捋这个思路。
19:01
那这边呢,有三个点。好有三个,然后呢,我把这个图也拉过来。不难吧,同学们好,我把它捋一捋。诶,这门有点问题,我把它往上提一提,好吧,提一提。走。好的,那最后代码实现写到这儿,代码实现。代码实现就是我们在eclipse里面写的这段代码,我给同学们板书到这里。OK啊,同学们,那关于弗洛伊德算法,我们就给同学们聊到这里,那下面呢,我们就准备给大家讲最后一个算法叫马踏棋盘算法,这个马踏棋盘算法非常玩,这里面呢,我们会用两种方式,第一种方式呢,我们就直接用。一种深度。我们直接会使用什么呢?直接使用这个深度优先发现效率很低,然后呢,我们还会对它进行一个优化好。待会呢,在下一个视频我们就讲解马踏棋盘,也叫骑士周游问题的一个算法。
20:02
这讲我们先给同学们聊到这里。
我来说两句