00:00
同学们,我们来学下一个算法,下一个算法呢,叫狄杰斯特拉算法。这个狄杰斯斯特拉算法它是做什么的呢?我们仍然以一个应用场景来讲解,大家可以看到这里有一个求最短路径的问题,什么问题呢?大家看这有一个图。对,仍然是以前我们用的这张图里面有七个点,现在的要求是这样子的,战争时期,胜利乡有七个村庄。ABCDEFG现在有有六个邮差,现在有六六个邮差,这六个邮差呢,从G这个顶点出发,从G点出发需要分别将六封邮件送到ABCDEF这六个村庄,就说有六个人从G点出发,然后然后要把我们的邮件送到abdfc这六个村庄里面去。
01:03
呃,那么同学们可以看到村庄之间的这个边呢,表示全。就是我们的距离,比如说A和B,哎,A和B,那这样子就表示AB这两个村庄的他们的这个距离呢,为五个公里。现在的要求是如何计算出G这个村庄到其他各个村庄的最短距离。注意啊,不是要把所有的点都走通,而是指的从G点出发到A。比如说有一个人,G到A最短距离是多少?G到D是多少?G到D是多少?G到F是多少,以此类推。那么呃,把这个做完了过后呢,他说如果从其他点出发,到各个点的最短距离又是多少?你比如说我从C点出发,也要到,也要到另外的六个村庄,请问最短距离是多少?就是这个意思,明白了吧。
02:01
OK,那你比如说嗯,你你到ABDEF这个比较好解决,因为它就一根线对吧,一下就能搞定,那么关键是你看G这个点到D,它就有两条路。哪两条路呢?我换一个颜色,比如说它从这条线可以到D,从这条线也可以到D,那么我选。GDD还是GFD呢?诶,这就要求我们求最短路径了,明白吧。诶,就是最短路径的问题,说白了,那最短路径的问题其实在我们现实生活中非常的有用,你比如说你在一个城市,你在城市,比如说你在假如说你在一个站点,比如说你在海淀黄庄。你在海淀黄庄,你要到另外一个站点,比如说这个站点是哪里呢,表示。平西王府,平西王府这站点里面有有很多公交站都要过,那你想你走哪条线是最短的?
03:07
是不是我们百度地图都有这种这种功能呢,说我做哪哪趟路,再转哪趟路,再转哪趟路就能到平西王府,那么距离最短。这其实底层就可以用狄杰斯特纳算法快速的把这个问题解决,其实还是非常有意义的,这个题好,那么问题提出来以后呢,我们简单的给各位同学说一下狄杰斯特纳算法的。一个介绍DJ斯特拉算法呢,是一个经典的或者是典型的最短路径算法,它用于计算一个节点。到其他节点的最短路径。那这个节点其实用这个解更好一点,对吧,我们一直用这个解,那就一直用这个解了,把改一下就行了。就是从一个节点到另外节点最终中心,它的最主要的特点是以它最主要特点是以起始点为中心,向外层层层扩展,其实这里面用到的就是广度优先的搜索算法,我们前面是不是学过图的广度搜索算法?
04:13
对不对,这里就用到广度优先这个搜索思想了,直到扩展到终点为止。直到扩展到终点为止,那么我们来简单的回顾一下这个广度优先,它是一个什么样的思想,我们简单回顾一下,打开我们的笔记,我们在哪里讲了广州优先呢?同学们。是不是我们在讲图的时候,这讲了深度优先和广度优先,那么最后我们讲完广度优先过后,这里是有一个比,就是深度和广度的一个比较,大家还记不记得,如果是深度优先的话呢,它是以一个点访问一个点过后再访问下个点,以这个点在作为新的出发点再往下面走,而广度优先的算法是一层一层的访问,就是我先从这个。
05:04
一号,比如说我们从一节点出发,先便利先去访问什么呢?诶先去访我们的第一层,就是二三,把二三访问了过后,再去访问我们的下面这一层,再去访问八,是不是这样子的呀,是不是12345678呀,那这种广度优先,其实在这里面就体现出能够去它这个地方的一个应用场景,就是我们可以求最短路径了。因为你一层层的去计算吗?对不对,那我当然就可以知道从这个点到我们的一个终点,比如说八最短距离是什么,因为我一层层的访问的。是不是,而且我在这个过程中肯定一个筛选的过程。好,这是广度优先算法的一个简单的回顾,那同学们回到这里来,再看一下它的算法大概是什么样子的。同学们看狄杰斯特拉算法的过程大概是这样一个过程,设置出发点为V。当然这个V呢,是你在程序里面指定的顶点的集合,顶点集合也是个大V,里面有V1 V2 V3,这个代表是否访问过,就是你这个顶点刚开始是没有访问的,然后逐一被访问,然后V到V就是V,这个是我们的出发顶点,V到大V的这个集合里面的顶点距离构成另外一个集合叫第四。
06:25
这个第势集合呢,它记录了什么?同学们注意听我说这句话,它记录了V这个出发点到其他各个顶点的距离。再说一遍啊,这个第十集集合里面放的是有第一,第二,第三,那第二,那第第第第以以此类推,那么第十集合里记录的是V这个出发点。就是出发这个顶点到图中各个顶点的距离,自身可以看作是零。那么V到V这个。距离呢?我们记为Di。好,这个大致的知道没有,也就待会儿呢,我们在这个过程中至少有两个集合要创建,一个是大V,这个大V代表。
07:08
代表我们访问过的。这个顶点还有一个DD是这个D时,这个集合能代表我们这个出发点距离其他点的距离,明白吧,好,它大致的思路这样子的,从D势中选取值最小的Di,并移出D势,同时移出V,这个集合中对应的VI为VI,这个是为最短路径更新地集合,更新规则是比较V到V集合中顶点的距离值与V。通过的VI到V集合中顶点的距离值,保留值较小的一个,就是我们总是把最小的保留下来,同时还要更新一个前驱节点,那也就是说我们待会儿还有一个集合。能够记录各个顶点的前驱节点是哪一个,重复第一步到第二步,直到直到最短路径顶点为目标顶点即可结束。就说我们访问到。
08:07
那个目标顶点了。同学们看,如果我们仅仅通仅仅通过这个文字来描述,大家很难理解,说实话,狄杰斯特拉的算法呢,比前面我们讲的克鲁斯卡尔算法。还有前面讲的普里姆算法都要困难一点。都要困难一点,所以大家做好一个心理准备是有一点难的啊,而且这个文字通过这个文字来描述,大家可能也不知道老师在说什么,那么我们先对狄杰斯特拉有一个基本认识,总结一下,大概呢,就是狄杰斯特拉,第一点你们要知道迪杰斯特拉是用来做求最短路径的,这点一定要明白,第二点,第二点,第二点呢,我们要知道迪解斯特呢,他用用的底层用的是我们所谓的广度优先的这么一个搜索算法,这个能理解啊,第二个要提出来,第三一个在我们实际操作算法的时候呢,我们会有三个三个数组。
09:01
哪三个数组呢?一个是大V。这个V呢,记录的是被访问过的顶点,还有一个diss diss呢是距离,记录我们这个出发顶点到其他顶点的距离,它肯定是在不停的变化,还有一个记录各个顶点的前驱节点的一个数组,也就是至少有三个数组要用好了。那关于迪杰斯特拉的一个文字描述就说到这儿,待会呢,我们再用图解的方式给大家再讲讲狄杰斯特拉算法的一个流程。好的,这讲先聊到这里。
我来说两句