00:00
各位。有了前面DJ斯特拉算法的基本介绍过后呢,我们就来开始来解决这个题了,就是把前面提出这个题呢,用狄杰斯特拉算法给大家进行一个编写和实现。嗯,T,我就不再念了,我们直接来说关于用狄杰斯特拉解决这一个最短路径问题的一个算法思路打开。这里呢,我做了一些准备,图解一下。这个地方讲的是狄杰斯特拉算法的思路图解,打开它,我们都一样。同学们可以看到。可同学们可以看到,在待会儿呢,我们会创建一个VI这样的对象实例,这个VI里面呢,有这么三个数组。一个是already already already already,这个里面记录的是什么?注意听讲哈,这个里面记录的是我们已经访问过的节点,如果是零,代表未访问,如果是一,代表已访问。
01:04
清楚了啊,待会我都有用啊,注意认真听,然后第十呢,再说一遍,这个第十就是刚才我讲到的,他记录了各就是出发顶点到其他顶点的这个距离。没问题吧,Pre visit的呢,代表它的各个顶点的前区顶,前驱顶点是哪一个?好,那这样讲可能大家很难理解,那各位同学请看啊,当我们注意听,当我们开始访问的时候,比如说。比如说我们。从哪个顶点开始访问呢?假如从G这个顶点开始访问,因为提的要求也是从G这个顶点开始访问,在还没有访问G之前,那么同学们可以看到already呢,是012345。这前六个顶点都为零,没有访问。当我们设置要开始从第六个下边为六的顶点及G这个顶点开始访问的时候,我们就先把它置为一。
02:08
但是这个时候还没有彻底的去处理啊,还没去完成这个访问,那么第十这个距离呢,可以看到,我们看这张图,同学们注意听。同学们注意听啊,我看看这张图,大家应该可以看得到吧,在这。待会儿我把这个往上面挪一下。这个理解起来有一定难度,注意认真听啊,同学们。我把这个挪到这儿来,大家应该就好看一点了。好的,跟上我的思路往上来走,看,大家再来看,跟着老师思路来看。第十这个数组呢,它记录的是各个呃,就是我们的出发顶点及这个G这个顶点到其他顶点的距离。到哪些定点呢?比如说是A呀D呀C呀D呀呀F啊,这样顶点的距离大家可以看到,当我们还没有开始访问准备工作时候,你会看到他在默认情况下可以看到。
03:08
初始化的时候注意听,初始化的时候呢,我们认为注意听啊,当初始化的时候,我们认为这个G到A的顶点为最大距离,65535。到其他顶点都是6535,就说先设置一个最大值,为什么呢?因为后面我要。在实际的判断中。将其逐渐的。更新,那么到自己呢,我们设的是零。就记这个顶点到自己设置是零,这个没有问题吧,我们再来看前区。前驱节点是代表就是你这个顶点的,上一个顶点是哪一个,就是从哪个顶点呢?访问到你的叫前驱顶点,那前驱顶点在没有进行这个访问之前全是零,这个也很好理解,好同学们看下面就有东西了啊,当。我们以G这个顶点,以以G为出发顶点,访问过一次以后,就是操作过一次以后呢,我们会发现这边就有变化了,来看一下,同学们认真听。
04:12
同学们可以看到上面没有变化。就是上面这个already没有变化,因为你现在只是访问G这个顶点吗?所以说你会看到其他顶点还没有访问过,只是一被访问过了,理解哈,各位同学好,这个做完了以后,我们看距离,就当把G这个顶点操作了以后呢,我们发现就有改观了。啊,这个算法真是挺难讲的。啊对同学们要理解,一定要跟上老师思路啊,就是我们原先初始化,这是不是都是6535,这个也很好理解,那么当我们把G点访问过一次过后呢,我们来看它是不是在访问过程中要看这一条线啊。是不是老师现在标红的这条线你们看见没有,那么G到A是不是就变成二了?诶大家看原先是6535,但是我访问过后,我发现G和A的实际距离只有二,而二是小于这个6535,于是就更新了。
05:10
看到没有,那同样。它和B的距离呢是三三,比原先这个记录的6535又小,于是又更新。看到没有,好,紧接着我们看第三个,当G和C进行控制的,呃,操作的时候发现G到C的距离为大NG653566535,并不小于原先的65535,因此呢,不用变化。当然下一个顶点也是一样的,比如说到我们的这一个6535,第三个几个顶点,它第三个第三个顶点其实就是我们的E了,E跟我们记呢,也是一个N的值,就是是是不可连通的,那么这边呢,也记录6535,因为你原先6535我并不比你小嘛。好,其他两个也很好理解,看到了F和GEAE啊,刚才那个说错了,是D,刚才是D啊,好,我们再来看E跟G的距离是是E跟F的距离是六。
06:15
你可以看到,因为四和六是小于65535的,因此这两个被改变。被改变,我们再看第六一个,第六个,你原先自己到自己是零,你访问完了过后,G到G还是零,因此呢,这个没有变化,于是当我们访问G过后,我们第十这个数值就变成了2365356535460,这个大家理解吧,你们先不要去管怎么实现的好不好,因为不太好讲这个玩意儿。啊。呃,我讲课一般都是比较。心平气和的算法呀,讲起来确实挺郁闷。好,有时候你知道你不知道怎么去表述这个好啊,所以说你看我们在更新这个地十这个数组的时候,主要是根据这个连接图来看你到底是不是小于它,如果我在下次访问的时候,我发现诶还有个距离比二三还小,那我还要更新。
07:13
明白吧,好的,那紧接着我们再来看前区节点又是怎么变化的呢?也很好理解,大家还记不记得,当你把这个访问完了过后,我们这个图,我们这个图应该是这样子的,大家有没有发现,注意听啊,我们A是可以跟下面的这几个顶点连通的,哪个呢?就是跟B。没问题吧,跟B可以连通,看B连跟跟A哦,说错了啊,G这个顶点我们来看G这个顶点呢,它是可以跟A联通的,可以跟B连通的,记不记得还可以跟哪个,从这可以看它跟。这条线是E,它跟E是连通的,没问题吧,它跟谁呀,它跟F也是连通的,没问题吧,好,它跟另外这三个点,就是你们看到的C和D,还有G呢,它本身这方是相当于是嗯不去处理的,好呃或者是嗯认为是不可连通的,你们有没有发现,当他做完了以后,你看到没有。
08:18
这个。前驱节点就是。这个下标为零的顶点的前驱节点是谁呢?就是六了,你下标为零的这个顶点是不是就是A呀?A的顶点就变成G了,而下标为一的这个顶点是BB的前驱节点,也变成六了,大家看到没有,而二和三下标为二和三的这个顶点,它们并跟跟这个G没有什么关系,因此呢,它并没有变化,大家看这两个零仍然没有变化,紧接着下面的四和五分别对应我们的E和F,它也是。前驱节点就是借于是也更新,那么这个嗯。
09:02
这个六这个五啊,这个五三和四刚才是更新的对吧。这个二二不更新啊,刚才是这个更新这个更新这个不动三和四更新五呢。5554。嗯,刚才说错了,这个二二是不更新的,二和三都不更新,四和五更新对不对,四和,因为这太小了,我有点看不清,看看对不上啊,有点大家看这个图就能看出来,就是C。D。是不是这两是N呢,因此C和D的前区节点呢,没有变化,仍然是零,到了这一个E和F,看到E和F其实对应的是这个线,我换一个颜色的笔,就是你们看到这个,还有下面这个,这个呢也更新了,变成了六,看到没有变成了六,也就是说我们E和F的前驱节点呢,就是这个G下边为六的G,那自己呢,哎,当然你自己的前区节点,那当然还是你自己了,所以说你看这你这他就不去管它了,应该是这样子的啊,看自己的前驱地点,因为你自己前驱地点我们这设的也是类似于不不能到达,所以说呢,它就设为零,就代表没有前驱节点这种这种意思哈,这种意思就说如果在扫描的时候,我主要是看它的前驱点是哪个,如果是零的话呢,就代表我们这个前驱点还没有确定。
10:31
或者是没有明白这意思吧,好,嗯,大致意思大家大概明白什么了吧,就是我每访问一次节点,访问一个G,呃,先以G访问,我就去根据实际情况来修改这三个数组。OK,然后这个第一次访问完了过后呢,同学们可以看到我们得到的这一个情况就是这样子的。000这个代表注意推,这个就是我们已经访问过的那个节点,而666666这个是代表前驱节点的那个数组,就是pre v zt的,那么大家可以看到,这样就能看出来,呃,下标为零的这个顶点的前区在这次访问以后变成了六。
11:17
即,即这个顶点后面,以此类推,那么同学们看到最后还有这一排打出来是什么?这一排打出来就是第十。就代表你当你访问完G点这个顶点以后呢,诶,我们发现G到A是二,G到B是3G到。嗯,C是无穷,就是不可连通,G到下面这个abcd也是不可连通,那么G到E呢是四,G到F是六,G到G是零。就代表我们这个地方零就是自己跟自己不去处理嘛,对吧,你自己到自己干什么呢?好这去写这个写了一个零,写了一个零就说访问一次就变这样子,那么注意听,你现在仅仅是访问了G这个顶点,那下面会继续选择并返回新的访问顶点。
12:08
那你这个G访问完了过后,下一个访问顶点应该是哪一个论呢?同学们就应该是A了,为什么?因为从你这儿可以看的出来,你既访问完了过后,根据我们这个呃,广度优先的话,你原先是既已经把。AB。还有一个EF访问完了,这个时候,这个时候根据我们广度优先,G已经没有办法再去访问到别的了。是不是因为他已经把他这一层。访问完了吗?这个时候他就去选他其中的第一个A作为新的新的这个出发点,再继续去访问A可以访问到的心地点,在访问过程中呢,再去实时的更新我们这三个数组。明白了吧?OK,但是一定要注意啊,当我们把G访问过后,我们返回新的访问顶点,比如说G访问完了过后,A就会作为新的顶,新的访问顶点开始访问,但是注意是这个A是新的访问顶点,并不是出发顶点。
13:13
这就是为什么我们要去记录这个前驱顶点的原因,因为待会我要把前区这个地点知道了,我才能把这个心的距离计算出来。明白这意思吧。注意啊,出发顶点是不会变的,就是G,但是你既访问完了后,下一个。访问定点是可能变化的,因为你是广度优先嘛,访问完了,你得选一个已经访问过的顶点,作为新的一个访问定点,开始继续往下一层访问,最后在便利所有顶点结束以后,我们就应该得到一个最终的第十。也就是说,最后这个结果一定是放在地势这个数组里面的,因为它记录了出发顶点到各个顶点的最短距离。好,那待会儿呢,同学们注意看到,待会儿呢,我们会怎么创建呢?我们会创建一个类叫V的。
14:05
我把这个改一下叫V。Visit的,呃,Ver text这个呢,就记录了三个数组,一个是already,记录各个顶点是否被访问过,动态更新,为什么动态更新呢?因因为你的顶点是一个一个访问的,一表示访问过,零表示未访问。说清楚了啊,还有一个数组就是pre visited的这个这个pre visit的是干什么呢?它的每个下标对应的值就是它的那个元素值啊,为前一个顶点的下标。直为前一个顶点的下标。啊,你比如说刚才我们以这个为例,我们以这个为例,比如说你看到他前区节点的数组是这样子,你应该怎么解读呢?就代表就代表,因为你这个你这个六下标为零就代表。就代表什么呢?就是零这个顶点的,注意听啊,零这个顶点的前区顶点四六下边为六的这个顶点,就这个意思好吗?好的,还有一个diss,这个diss就是刚才我们看到那个,它记录出发点,就是我们这个出发顶点到其他顶点所有距离,比如以G。
15:17
为出发顶点就会得到记录,G到其他顶点距离也是动态更新的,最后我们求的最后求出的最短距离就会放在DS里面去。啊,其实所以说这个核心点,其实就是对这三个数组的动态更新。那么根据实际情况就来更新就可以了,好,同学们,那关于我们狄杰斯特纳算法的一个思路图解先跟大家聊到这可能呢,大家不是完全听懂了,对吧?你你现在大概应该知道我们的杰斯特大的一个算法的基础,其实就是不停的在根据我这个设计来更改我们already,还有diss,还有pre visit等。那么它更更新的这个原则就是找最短的这个距离,在广度优先的基础上找最最短距离,最后我们这个结果,当把所有的顶点都访问,都操作过后呢,我们这个diss里面存的这个值就是代表我们。
16:18
这一个出发顶点到其他顶点的最短距离。好,分析就到这里。
我来说两句