00:00
各位,我们对狄杰斯特纳算法做一个小结,呃,我们先来看一下,刚才我们呃解决从G点,就是从G这个点。到其他各个顶点的最短距离,我们已经算出来是这样一个结果,而且验证是正确的,那么我们换一个出发顶点,看看是不是也是一样的呢?比如说我把这个出发顶点换成C,我看看以C为出发顶点,然后看看到其他的六个点的距离是不是也是正确的?来,我们先试一下这个算法,那现在我们只需要把这个六换成几呀?因为现在你出发力你是C了,那这个下标经就应该是二,为什么是二呢?因为你ABCC的下标对应二,我们来运行一下。运行完了之后,我们发现这个结果好,先全屏再运行一下各位。那我们最后这个结果呢,是这个样子的,对不对,我们看这个结果跟我们呃想的是不是一样,来验一下。
01:03
同学们,跟上老师思路,我们来验一验。首先A到a.C到A。七是最短的,肯定这个是正确的,到B这个点呢。到B这个点是不是这这条线最短,我换一个颜色,同学们我换成红色。这样子是不是最短呀,那这个应该是。12。没有问题吧,同学们是不是12,那有些有些同学老师我这个CAC到A再到G再到B,那也也是12吗。也是12,我这里没有把这个路径打出来,其实同学们可以自己把路径打一下,因为你每次在遍历的时候,这个路径是能够记录下来的,对不对,反正它是12是最短的,我们看C到C呢啊,知己到自己当然就是零了,也是正确的,C到D这个有点远C。到这个地,那这条这种线就很多了啊,这这是一条,这又是一条,这是那多了很呢。
02:05
呃,你们大家去看一看,其实最短的是哪条线和这条线。这样走是最短的。是八加五再加四等于多少呢?等于17,正确的。到E这个点最短是哪一呢?当然就是单根线呢,就八也是正确的,到FF这条线呢,肯定这样是最短的了,是不是?那就是13也是正确的,到G这个点呢?有两条线可以走,一个是CG9 CG12,显然九是最短的,因此我们验证出来以以C为出发顶点,到其他六个点的最短距离也是正确的。也是正确的,好,没有任何问题,好,那同学们如果有兴趣的话,可以把这个路径用一个数组把它保存起来就可以了,好吧,这块呢,我就不去写它了,因为核心的已经写完,那现在我们把刚才讲的内容做一个小结。
03:02
给大家板述一下,刚才我们为大家讲解的算法是狄杰斯特拉算法,大家可以看到狄杰斯特拉算法呢,会相对麻烦一点,对不对?它的复杂度会高一点,我们来捋一捋这个思路吧。我们怎么来讲狄杰斯特拉算法的呢?我们回到这边来,首先我们仍然是抛出了。诶,我们我们仍然是抛出了一个应用场景,是这样子的吧,就是我们的老老套路,先给大家看了一个应用场景,说白了就是求最短路径,求图的最短路径是不是。那这个应用场景呢,对于我们来说并不陌生。其实前面我们。修路问题也是用的这张图。对吧,诶,那这个图呢,我也给各位朋友拉过来。好,这是我们有这么一个问题,引出了狄杰斯特拉算法的这个。
04:05
这这个算法,当我们把狄杰斯特拉算法引出来过后呢,我们就给同学们简单的介绍了一下狄杰斯特拉算法的。一个思想是什么样子的,对吧?首先呢,狄杰斯特拉算法,它是一个典型的最短路径算法。它是用于计算一个节点到其他节点的最短路径,最主要的特点是使用了广度优先的搜索算法。而在刚才演示的过程中,大家可以看到,我们的确使用的是一种广度优先,就是先把A能够访问的所有顶点走一圈。走完,然后再去选一个距离更小的,再去找它的它的顶点,最后直到扩,扩展到我们每一个顶点就完事了。好的,那这个狄杰斯特拉算法过后过,我们有把狄杰斯特拉算法的一个过程给各位朋友做了一个介绍。
05:01
当然,因为这个算法的介绍呢是基于文本的,所以说同学们听起来应该是相对比较吃力的,很多同学可能也没听懂,于是我们就用图解的方式再说了一个,就是。我们在讲这个应用的时候,先用图解的方法说一下我的思想,那个时候就应该相对好像容易理解了一点,对不对,就相对容易理解了。那我们在讲这个题的时候呢,我们是怎么做的呢?诶先把这一个图拉过来。对,然后拿过来过呢,我们第一步先图解了,就是使用图解的方式分析了。这一个狄杰斯特拉算法的。一个思路。对不对,它的一个算法的思路是什么样子的,我把这个图解,图解的这个部分给大家拿过来,其实说白了就是这张图。是不是就这张图我把它放小一点啊?
06:02
放小一点,这样大家就看的比较清晰了。就是我我先把这个思路给同学们聊一下对不对,说我们初始化有这么一个东西,经过G点访问以后呢,变成了这样一个东西,然后变完了过后,我们下一步又该做什么,他每步是怎么变的,我在。讲解这个思路的时候,说的还是比较清晰的,如果你忘了的话呢,可以把那一节儿拿出来再听一听。你多听几遍就应该很清晰了,同学们没有办法,这个是有点难度。然后呢,这个分析完了过后,我们就用代码实现了,对,把这个要求先写到前面去吧,先把要求写到前面去好吧。这是我们提的要求嘛。粘过来好,这边我把编号重新编一下就可以了,对不对,五。这是我们的思路,那思路完了过后,下一步是不是就是我们的代码实现了六。就是我们用代码实现了一把,代码实现也非常简单,那代码呢,在哪里呢?代码是一个整体,写在了这一个文档里面。
07:08
大家可以看到这段代码的量也还是不小的,如果加上我们注释,也将近有200行代码。说说难度,应该说还是有一点,就说你如果在嗯,在不看老师的代码这样一个前提下,自己能够很顺畅的写出来,应该说还是需要一点功力的,对,那证明你的头脑已经很灵活了,就是这个人很聪明对不对那。这个呢,大家要去多看几遍,可能才会深入的理解好吗?那老师就说到这儿。好,这是我们关于迪杰斯特拉的算法的一个介绍,那下一个视频就为大家准备,讲讲弗洛伊德算法。关于弗洛伊德算法呢,我们。下一个在下一章节再为大家进行介绍。
我来说两句