00:00
同学们,我们来用代码给大家实现一下弗洛伊的算法,我们还是用求最短路径来讲解。弗洛一的算法的实现。提的要求呢,我们再简单的回顾一下,说有七个村庄,分别是ABCDEFG,那么各个村庄边呢,它已经告诉你了,这个边就代表我们的距离。现在呢,要求求出各个村庄到其他村庄的最短距离,注意听这里面人家要求是各村庄其他各村庄的距最短距离。显然使用。狄杰斯特拉算法就不太合适了,因为迪J斯特拉算法呢,它是求出某一个顶点到其他顶点的最短路径。现在我们要把每一个顶点都当作出发顶点来进行。这道题的一个完成,那现在呢?我们显然用弗洛伊的算法是最合理的,对吧?那关于弗洛伊的算法的思路,前面我们已经图解了一把,现在我们直接走代码,打开eclipse,我们来写一下。
01:07
新建一个包,各位新建一个包,弗洛伊德。简写一下。Flow。ED。对吧,用这个单词来表示loed的fluid的这么一个算法,现在呢,我们新建一个类。各位朋友,我们新建一个类。这个类的名字我们叫fluid,然后呢。Organism。对,用这个类来表示,我们写的是洛伊的算法。把主方法勾上。好的,那主方法勾上以后呢,我们就开始来写,那首先我们还是老规矩,先要创建我们的图。对不对,创建这个图来,Class跟着我的思路。Gro。那作为作为图来讲,我们需要哪些属性呢?非常简单。
02:05
叉这个地方是一个数组,认为是我们的顶点,好吧,Text。这个是干什么呢,存放顶点。顶点的一个数组。对,存放顶点的数组,紧接着我们再来定义private,那这个地方我们也可以写成private。没问题吧,Private,好,那现在这边int我们是不是有在整个这个分析过程中,同学们有发现我们是需要有两个数组的,一个数组呢,距录的是距离表,一个数数组记录是前区关系是不是好,所以说这两个数组呢,我们先把它做出来,第一个数组就是我们的地势。写出来,我写一个注释。全屏一下第十这个二维数组干什么呢?它是记录或叫保存都可以保存什么呢?保存。
03:00
呃,从各个顶点顶点出发到其他顶点的距离,也就是说最后最后这个结果也是保留在该数组中的,这个大家是不是在刚才分析的时候已经知道了,在private仍然是一个二维数组。那这里面P,那这边我们写的是这个P是记录什么呢?到达这样写啊,保存保存到达。对,到达什么呢?到达目标顶点的前区,OK,前驱顶点这个数组呢,也是在动态变化的啊,就是说Dis和P,刚才我们讲过,它是在动态变化的。动态变化的,这是在动态变化的,那现在呢,我们来写一个构造器,构造器,那构造器非常简单,我们写一个grab。
04:00
那构造器,你构建这个图需要给我传什么信息过来呢?好的,首先你得传一个Les。就是你有多少个顶点得告诉我,紧接着呢,我们再来写一个。你传给我一个什么呀。Matrix。这个matrix就是我们的临界表,这个临界表可以直接付给第四就可以了,对不对,Matrix。好的,那这个有了过后,是不是我们还有一个二位数组,对吧,这个数组来不着急写到这。这个数组呢,就是记录我们的,呃,这个数组就应该是直接把。因为你这个P这个数组呢,是我们动态生成,所以说这个地方没办法传进来,没办法传进来,我们先写到这,你要把顶点数组传给我,是不是你的顶点的情况要告诉我。好,行吧。好的,那么这个这个地方应该怎么来写一个注释呢?我们写一下这是长度我的大小。
05:06
这边就是临街初始的这个临街矩阵。没问题吧,下面这个就是顶点数组。哎,顶点数组这个也很好理解,那下面呢,我们就来。编写里面代码,首先this.vertex它就应该等于什么呢?Vertex就是你把这个顶点数组传给我,我就接收嘛,再来this.dish就应该等于。Metrics。是不是我接收你这一个临接矩阵,还有呢,就是我们要得处理这个事情的同学们看啊z.P同学们知道这个P是保存到达目标顶点的前序定点,那这个呢,它是动态生成的,所以说我们在这溜一下。六一个这样的数组,那么这个数组大家可以看到它的它的这一个行和列,其实就是跟你的顶点的个数是相关的,所以说我们这一张直接把N传进来就可以了。
06:12
就是以你顶点的个数来进行创建完事。好,嗯,这边这边写完了以后呢,下面我们就应该for循环一下进行初始化。我们对什么呢,来对。对,这个P。数着初始化。OK。初始化。那怎么初始化呢?大家看到在我们还没有进行这一个便利之前,其实各个顶点的,呃,全区顶点就是它自身是不是这样子的,所以说我们要初始化一下,不然的话,那那它就是全是零了,全是零那这个P里面定定的是。记录的是它前驱顶点的下标啊,注意这一点,注意点不是直接放在A和B,注意。
07:01
注意存放的事。注意存放的。是前区,前区顶点的下标并不是直接存放的,像这个abcd知道吧,哎,我这边要说清楚了。好,现在呢,我们负循环一下就可以了,In。I等于零,I小于什么呢?朋友们,小于这个N是这样子吧,I加加。没有任何问题,那这个地方我们就简单一点,只用A给它填充一下就行了,给不你看我怎么填充啊,首先我要往这个地方填一个数据进去,怎么填呢?就填他自己。这大家能理解吧,就说如果你是下标为零的这个顶点,那么你在初始化的时候呢,你的这个顶点就是你自己,所以说也就是I,如果你的下标为一这个顶点,那你初始化的时候,你的这个顶点也就是下标为一的这个顶点。
08:03
好,这个时候graph就写完了。那写完以后,同学们,我们是不是。可以来秀一把,因为待会儿呢,待会儿要演示嘛,所以说我来再再写一个显示方案。显示方法就是能够显示哪两个呢?显示地势数组。和。OK,显示这个吧,显示pre数组和第四数组。因为到时候我们要看结果嘛,肯定以这两个数组是主要的,所以说我现在写一个public VO show,跟上我的思路。大家都知道我们P第它是一个二维数组,所以说其实你用一个for循环就行了,两个嗯,双层for循环就搞定,对不对?那下面呢,我们来写一下这个数吧,那就for循环NTK等于零,K小于什么呀。K小于什么?同学们是不是小于?呃,小于哪个呢?第十点认。
09:04
因为你将来这个嫩子本身大小,你大小的是大小呢,就是从这个嫩就可以拿到嘛,K加加K加加好的。呃,K加加完了过后我们先显示啊,先将哪个呢?P数组输出,那这个就很简单,在负循环一下,Anti ti等于什么呢?朋友们,Anti ti等于零,I小于什么呀?I是不是还是小于Dis点啊。因为你原先就这么大爱娇娇。那A加加完了过了,我们就简单一点输出,怎么输出呢,就是。来KI就可以了。是不是这样子,为了好看,打个空格写完了。那写完过后呢,我们再去便利我们的哪个哪个呢,再去便利我们的这一个,呃,地势数组。再显示地势速度。
10:00
你可以这样再写一遍,但是大家有没有发现这个有点啰嗦,为什么呢?因为你这个K已经取了一次,你再去写一遍没有意义,所以说干脆呢,就直接在这顺带。你显示一行pray。数组我就在显示一行,第十数组的一行数据就完了嘛,没有必要写两个for循环,明白吧,一般会这样去啊,这个是输出pre数组的一行。的一行数据,好,我在输出数组的一行过后呢,我就输出。输出哪个呢?历史数组的一行数据。给它对应。啊,给它对应,那就for循环int对应啊,I等于零,I也小于什么呀,小于Dis点。哎,佳佳。I加加,那这块显示也非常简单,System。是不是,那怎么输出啊,同学们是不是就是Dis。
11:02
我们的K。I。再加一个空格就完事了,那这样子写完了过呢,他们中间最好有一个换行,不然的话就打成一坨了,同样我们每输出一行呢,我们也换一下行,这样好看,多换一行。那大家看。在输出一个数据的时候呢,没有必要换行,所以说这个地方我们就把LN拿掉就可以了,同学们一个显示的效果就写完了,特别简单,那我们来试用一下,测试一把。呃,弗洛伊的算法还没有写,同学们,我们现在仅仅是把图创建起来,起来了而已,对不对?先测试一下测试看看。图是否创建成功对不对?先把这个念一下创建成功来跟上我的思路。嗯,首先呢,我们把顶点先创建起来,顶点数组先创建起来ver text。
12:04
等于什么呢?朋友们好,就应该等于A。是不是前面已经说过这个了B。C。C。D。好的E。F。G。G。好,我把它格式化一下,那看的比较清晰一点。格式化一下,那拿到这个。顶点数组以后,是不是我们还有一个,还要创建一个什么呀,是不是要把最原始的我们的这一个叫做。临接矩阵创建起来是这样的吧,同学们好,我们现在创建临接矩阵,创建临接矩阵。好创建吗?非常的好创建啊,来,我们写一个int。找找等于什么呢?诶,May matrix。
13:00
Matrix trickx是这样写的吧,Matri等于六一个int大小是什么呢?Vertex。点N是这样子吧,同学们同样vertex.n因为你你这个矩阵的行和列呢,实际上是由你的顶点的个数来决定的,所以说我这显的是verex length没问题吧,现在呢,给它再定一个final,大家知道在我们表示两个点无法直接关联的时候呢,用的是N表示,这个N呢是一个较大的值就可以了。对,让我写一个大写的N。定一个相对大一点的吧,咱们就六。6553565535就可以了,好吧。现在呢,我们还得给他把关系写好。这个关系就是。同学们看到的一行一行的数据。那这个呢,因为比较啰嗦,所以说我这已经有有一个数据的准备了,我就拿来用一下,好吧,同学们没问题吧,同学们我就拿来用一下就行了。
14:04
这块呢,已经准备好了。其实原先我们也是用过的。整理一下我们的代码,大家看一下老师这这写的有没有问题。057NNN2看一下。057NNN2正确,550N9NN3,再看第二行对不对,50N9N3,那没问题,好这就可以了,然后呢,我们现在创建。创建什么呢?我们创建一个土对象。很好理解吧,六。那这时呢?我们把Les matrix和verx一并传给他。那怎么传呢?同学们认识很简单,其实就是我们ver text认,其实就是七。然后我们得到一个对象,好,我们显示一下点数。
15:01
来部分要运行。运行过后呢,我们可以看到情况大致是这样子的。000。057655,哎,没问题吧,没问题,距离也是对应的,那同学们注意我这样写呢,嗯,没有什么问题,没有什么问题,但是这个阅读性很差。阅读性比较差,因为我们我在刚才已经分析过了,就是你将来这个这一行。这一行,这一行分别代表的含义是什么?我前面讲讲过没有,我说过,如到将来,这个位置代表的就是A到A的最短路径,而这个点代表的是A到B的最短路径,是这样子吧,同学们。这样子的话,我这不我这样子干脆就直接把这个信息也体现到这里,明白我的意思吧,所以说我要对显示呢做一点改进,因为我这样子写,我自己也看的很很啰嗦,比如别人问我这个点代表什么含义,我还得去看,哦,这是第几行啊,就是ABC哦,这是第三行C。
16:08
呃,再数一下这个是。Abcde,这是E,然后我就告诉别人说,哎,这是C到E的一个最短路径,太麻烦了。对不对,太麻烦,因为他最后经过你的弗洛伊的算法过后,他就是这个结果,他就是他就是最终结果就是存到这了,但是现在这个不一定是对的啊,现在你只是初始化,还没有弗洛音的算法来走呢,但是阅读性不好,所以说我把它改进一下。怎么改进呢?我在这来给他改一改啊,就是为了显示便利,为了显示。呃,易于便于阅读。便于阅读,对,便于阅读,我们我们优化一下,优化一下输出,好吧,那怎么优化呢?非常简单,我把这一个数组顶点拿过来。诶,这个顶点的一个数组,我先拿过来用一用。
17:05
呃,怎么怎么用呢,怎么用呢,大家看啊,我在这儿要变一下了,因为你这个点呢。其实是顶点的下标,所以说我就很简单了。Vertex,你看这个很巧妙哈,Vertex把它包一下就完事了。是不是,如果我这样一输出,大家是不是再一看你看看起来就很舒服了嘛,哦,这边是。第一行,诶,它的里面是这些。第二行、第三行,地上看起来比较舒服,同样道理,下面也可以改写了,咱们怎么改写呢?这样改写来跟着我的思路。那首先我们这样提示他一下说。可以先写一个。呃,就是某某,比如说我这样写这样写写写写啊A。到。是吧,写A到B。的最短路径。是。
18:01
是不是最短路径就是这个呀。对对对,你现在要改的呢,就是仅仅把这个改一下,把这个AAB这个地方修改一下就可以了,好,现在为了好看,我把这个刮起来。是吧,最后这边也把它括起来,明白我我想干什么吧,如果我这样写完了过后,你看到时间这个结果呢,就会变成这个样子,看起来比较舒服,就是A到B的最路径,A到B的A到BA到B是吧,就是写死的嘛,待会把它动起来就行了,好,我改一改,现在呢,把这个A换了。换成什么呢?换成什么呢?同学们想一想应该换成什么是不是?我只要选择ver text?K。就行了,为什么?因为你现在正在变定的是K这个顶点嘛,因为你零到第十认识这个K其实是从零到六嘛,那零就是这个就是呃,当前这一行是对应的哪一个顶点嘛,那B应该是哪一个呢?B是不是就是当前这个I啊好,所以说你在这稍微的改一改就完了,叫ver text什么呀。
19:10
朋友们,这边应该写什么I就可以了。是不是好,这个代码就写完了,我们再来看一下效果。再看一下,你看这就比较OK了,A到A到BA到CA到D好,B到A到bab到CB到D好,下面再看一个记到A记到B,记到C到时间呢,这个就一目而了然,只是有些同学老师你这个路径还没有改,是的,我还没有做福一的算法呢,我只是把这个显示,还有我们这个构建图形的代码给各位朋友写完了,大家看这块理不理解?好的,那现在呢,我们就已经把准备工作做完了,也就是说我们可以把图创建起来了,而且我们把显示这个效果也做出来,下面呢,就用弗洛伊的算法,把这一个三个循环给他,一搞代码就完成了。
20:03
关于弗洛伊的算法的代码呢,我们放在下一个视频为大家讲解。
我来说两句