00:00
同学们,我们接着讲下一个算法。下一个算法要给大家讲的是弗洛伊德算法。那么弗洛伊德这个算法是什么呢?我们来看一下,首先我们看弗洛伊德这个算法它的呃,主要的作用是干什么的?他和狄杰斯特拉算法是一样的,弗洛伊德算法呢,也是一种用于寻找给定的加权图中顶点间最短路径的算法,也就是说弗洛伊德呢,它是。它也是用来求最短路径的一个算法。那这个名字为什么叫弗洛伊德呢?同学们都知道,在这个历史上呢,有一个特别有名的心理学家叫弗洛伊德,但这个弗洛伊德不是那个心理学家,他是谁呢?这个算法的命名创始人之一叫弗洛伊德,他是。七八年图灵奖获得者,斯坦福的一个教授,他的名字叫罗伯特。
01:03
弗洛伊德,因此呢,就以他的名字命名这个算法的。这个算法比较巧妙,同学们待会在讲解过程中你会发现弗洛伊德这个算法很巧妙,理解起来比较容易,代码写起来也很轻松,没有像我们前面讲的那一个狄杰斯特拉算法那么麻烦。它比较巧,也比较好写,呃,但是呢,它的这一个时间复杂度是比较高的,所以说同学们在后面讲讲,我在实现的时候,大家注意听就可以了,弗洛伊德这个算法呢。它是计算图中各个顶点之间的最短路径,什么意思?听我说啊,听我说我对这句话的解释,呃,弗洛伊德是计算各个顶点之间的最短路径,那也就是说,我们以这个图为例。我们以这个图为例。
02:00
N这个弗洛伊德它是干什么呢?它会求出A这个顶点,注意听啊,就是A这个顶点到其他六个顶点的注意段路径,就是以A顶点为出发,顶点到。另外六个顶点的。最短路径是多少?紧接着呢,它还会以B这个顶点为出发顶点,再去求出从B这个顶点到其他六个顶点的最短路径。以此类推,它会求出C这个顶点到其他六个顶点的最短路径,所以说同学同学们可以看到,我这里写的是它会求出各个顶点间的最短路径。而狄杰斯特拉算法它是干什么的呀?狄杰斯特拉算法它是计算图中的某一个顶点到其他顶点的最短路径,大家看到他们的区别没有?大家看到没有,也就是说的切斯特呢,它是指定一个顶点,比如说G这个顶点,它求出G这个顶点到其他各个顶点的最短路径就完了。
03:07
而我们弗洛伊的算法呢,它会把每各个顶点之间的旋转路径全部求出来,所以说同学们看,我这里有一句话。对比了弗洛伊的算法和狄杰斯特拉算法的区别,那同学们注意看这句话的一个整理。狄杰斯特拉算法通过选定的。被访问顶点,求出出发顶点到其他顶点的最短路径。比如说我们选的是G,那么就求出G这个顶点到另外六个顶点的最短路径。OK,弗洛伊德算法呢?它是弗洛伊德算法中每一个顶点都是出发顶点。那比如说你现在有七个顶点,那七个顶点都会作为。都会依次的作为我们的出发顶点明白,所以他需要将每个顶点看作被访问顶点,求出每一个顶点到其他顶点的最短路径,说他一次全部就搞定了。
04:09
所以说他这一个算法呢的特点跟狄杰斯特拉是不一样的,狄杰斯特拉斯求一个,而弗洛伊德是把所有顶点。到其他各个顶点的最短路径都求出来。好的,这点是同学们一定要注意的。小型面试官,他问你。弗洛伊的算法和狄杰斯特拉算法的区别在什么?你只要把这句话答上来就可以了。把这句话你就说,你就说,迪杰斯特纳是选一个顶点,求出这个顶点到其他顶点的最短路径,而弗洛伊德呢,是把每个顶点都看作出发顶点,求出。到其他顶顶点的最短路径完事。那么我们来看看狄杰斯特拉算法的思想是什么?同学们先看一段文字描述。它的这个算法呢,是如此这般的设置顶点VI,就说比如说我这有有一个顶点,这有个顶点,这是AB明白。
05:10
那么它设置顶点VI到顶点VK的最短路径为已知的lik,注意看这个明明是怎么来的。L代表论。就是它的长度。I代表D个顶点,K代表DK的顶点。假如VI到VK的最短路径已知为lik。又知道顶点VK,就是这个VK,这个顶点到VJ的最短路径为LK节。这个命明的方式跟前面一样,L代表NK代表K这个顶点,截代表截这个顶点。那么顶点V到VJ的路径呢?我们记为Li节。则V到V节的最短路径就是,求什么呢?这两个路径的和和Li节哪个更小?
06:08
那么我就把这个最小值记录下来。VK的取值为图中所有的顶点,即可获取V到V截的最短路径。大家知道我在说什么吗?大家可能不太清楚,我举个例子啊,比如说这有个顶点为I。明白。这有个顶点为K,明白这还有个顶点为节。明白好了。那么他先把这段路径最短路径求出来。因为这里面我画的只是两个顶点,中间它可能就是这个I和K,中间可能还会有其他的一顶点,我就没画了,他先把这个记录下来,叫Li。K明白。那么再把这个K到截的最短路径求出来,当然了,K和节之间可能是直连的,也有可能中间有其他顶点。
07:04
我这画的比较简洁,那么把这个路径我们记为L。K结明白吗?好的,然后。L相当于说我这个I这个顶点,通过K这个顶点到达截这个顶点,它的总的距离就应该是这一个值。我换一个颜色,就是同学们看到的LK加上LKG这这两个距离的和,是不是就是相当于以K作为中间顶点来处理的?这个距离我们就得到,还有一种可能性是,如果他们本身就可以相连,因为I和K呢,它本身是有可能直接可以连通的,当然也有可能是不能连通的,不知道。所以说把这段距离呢,我们记为什么玩意儿呢?Lig明白这意思了吧?
08:01
那么现在我就比较那么I到截最短路径到底是谁呢?如果这个小,则最短路径就是Li节,如果这两个数加起来就是LK加上LK节,也就是说我通过这个中间顶点到达的距离更小。那么我就把这个和。即为他们罪的路径,明白了吧,当然我再说一遍啊,注意听讲,I和K之间呢,我这里画的比较简洁,就好像感觉I和K直接相连的,但中间也有可能经过了一个距离,所以说它这里面有有一句话,至于。V到VK的最短路径K,或者VK到VJ的这个最短路径是LKG,也是通过同样的方式获取的,也就是说他们中间为什么这样短呢?也是通过我们刚才这种方式来获取过,因为中间有可能还有别的定点,我这是直接直接拿到两个比较。
09:02
中间没有顶点的情况来说的,帮助大家理解,而你实际得到I和K的顶点呢,有可能是通过循环D循环循环和迭界迭代,拿到这个举例的,明白我的意思了吧。好,这只要弗洛伊德把这个顺序,把我们所有的顶,有的这个顶点都作为出发点进行一个便利,过后呢,我们就把最后这个结果拿到了,所有的同学们可以看到它应该是经过了三层for循环。我们待会儿还会讲这个图。我这样讲,以文字的方式来讲呢,我相信大部分同学可能听了一个大概说,哦,韩老师,我大概明白了,就是呃,我找一个中间顶点K,然后呢,把它们距离先求出来,谁把它距离先求出来,再求出K到截的这个最短路径,然后呢,呃,我再看I和J他们之间直接的路径谁更短,如果谁更短,就是它的最短路径。
10:00
你就明白到这个地方就可以了,当然了,这样讲肯定同学们听起来就是很抽象,待会呢,我们再用图解的方式,就是画图的方式,再给同学们说一下弗洛伊的算法是怎么来的。OK,那关于弗洛伊德的基本介绍先给同学们讲到这儿,一会儿呢,我们图解一把弗洛伊德算法。
我来说两句