00:00
现在呢,我们接着往下写代码,还有一个重要的方法。来。你现在已经把这个V的ver t已经创建起来了,但是你还没有去真正的操作这个访问,好下面呢,我们有一个动作来跟上我的思路,这个方法叫什么呢?更新,注意听这句话啊,更新index下标。下标顶点,下标顶点到周围。周围顶点的,顶点的距离和什么呢?和周围顶点的。前区,前区顶点。啊,同时这句话的意思就是说,你你访问完这个G过后呢,你要把整个这个。更新一下,那我现在把这个方法写一遍,大家看能不能理解喽,PU可以写成私有的private void的up,你把什么传给我,把这个索引传给我。
01:07
好的,我的代码呢,其实很简单,几句话就写完了,大家看一下,那我先初始化为零。好不循环,这这个地方稍微有点麻烦啊,解等于零,解小于matrix。Max什么呢?Inex什么呢?点N好节加加。也就是说,也就是说你现在这个index下标为六,相当于说你现在要把这个六的这一圈。你的20啊,就是说相当于说你现在已经16了,六跟ABCDEFG,它的关系是记录在我们这个临界矩阵的,那么你要便利临界矩阵的这一行。然后根据这一行里面的每个元素来去对我们这三个数组进行更新,理解了吗?所以你看我这有个for循环。
02:06
啊,也就是说要去便利,这样写吧,根据便利。便利我们的临街矩阵。临街距。矩阵。的哪一行呢,就这一行。为什么遍历这一行呢?因为你你现在不是正在考虑你这个index跟其他顶点的关系吗?说只编辑这一行就可以了,那现在我们来开始玩一把,好,我先把这个认识记下来。好,大家看一下这个代码是怎么写的啊,点get这个VV。微微看微微有没有啊。呃,我们看一下。这个地方。这个地方呢,稍微有点麻烦,因为这个VV。哦,这个图里面还没有拿到这个呢。因为你你这个你你还没有把这个创建起来,就是还有一个这个没有创建起来,所以说我们这。
03:09
我们这个地方啊,同学们少了一点东西,你看你这个微微。你在狄杰斯特拉里面创建一个这个数组的时候,你在这创建了,我在这访问不到。这就有个麻烦事,那怎么办呢?那怎么办呢?同学们,非常简单,我们把这个做成我们的一个什么样一个图,就是graph里面的一个属性就可以了,这个能理解吧,也就是说我我现在只要加一个这样的东西,这事就搞定了,加一个什么呢?加一个这样的东西大家看。那能否理解啊,我看看加一个在graph里面,我们加一个属性,加一个什么样的属性呢?加一个这样的。Ver tax。微微。这样就好办了。
04:01
这个表示什么呢?这个表示已经访问的顶点的集合,那也就是说这边我们把这个就去掉了。在你做底进四拉算法的时候呢,先初始化了,那这个时候这个VV在这就可以拿到了,对吧,那就代码就好简单了,VV点盖的地势距离inex。Index。这句话大家知道是什么意思吗?这句话就是我先到已经有的这个第十数组里面去获取顶点到这个index的距离,再加上一个。再加上一个什么呢?好max现在的一个距离,因为你是广度优先嘛,你除了要把。原先已经统计的距离,拿到过后再去获取当前这个因这个距离,因为它是广州优先一层层往下面走的,好,这个大家看能够理解。这个距离是什么距离啊?哎,不好讲的很,这玩意我再说一遍啊,这个嫩是表示什么意思,我说一下。
05:07
就是。啊,这个句这个认识,它是它的含义是这样子的,注意听它的含义是。啊,含义应该怎么说呢,含义是。就是出发顶点。出发顶点。到index顶点。顶点的距离。距离加上。加上什么呢?从index这个顶点,顶点到截这个顶点的距离。据。距离的和。我不知道这个说清楚了没有,就说你因为你是广东一些一层一层往下面算的嘛,那你首先得把已经统计出来的距离先拿到,拿到以后呢,再去把你这个index一个顶点到截的顶点。
06:07
算起来就是现在最近的距离,就好像你这么理解,就好像A,你原先是借。记到A了。A到下面有个B,有个E,有个F,好,那你A下面比如说又到了,到了另外一个点,A比如说到了K这个点,那你原先这个地这个距离呢,已经被记录到了这个位置。那你现在记到K,因为你还要记录。最你你要记录到各个顶点的最最短距离吗?那现在假如我要记录这个K的顶点,是不是我得把这个距离加起来,才是记到K的一个真真实的距离,是这意思吧,所以他要加一遍,他加一遍,而且这个过程是一个循环的过程。好的,那这那如果说这个拿到以后呢,我们再做一个判断什么呢?注意听,如果这个VI ViVi in。
07:03
这个index,这个这个节啊,这个节如果他没有访问过,就是你当前这个节这个顶点没有访问过,并且还瞒足这个嫩,它干什么呢?它小于v.get。注意听vi.get诶这个地方V v.get d是什么呢?解好,这时我就要更新了。那我把这句话再说一遍啊。如果。如果什么呢?如果结这个顶点没有被访问过,并且。注意听,并且这个嫩就是我刚才说的这个统计出来这个嫩还小于什么呢,它还小于。它小于出发顶点。出发顶点到截这个顶点的距离就需要更新,就需要更新,因为有一种可能是你先统计了,但是人家从另外一个方向去还要近一点,就打个比方吧,说假如你原先是G。
08:14
到A。原先的距离是比如说比比如比如说是四啊,比比如说是四。但是呢,我我们发现发现就是。他到还有一个顶点,比如说是。呃,你打个比方有,呃我我怎么描述一个意思呢,比如说有一个B。好有有一个C,它也可以连到这,那么假如我,嗯,假如我有这么一个情况,就是我这边是一,这边是一,打个比方啊,比如说我G从这连起来是一,再从这一,诶我发现G到A呢,其实二也可以到达。那我就要更新原先这个最短距离了,大致这个意思啊,只是他有可能是往下走的,我不好描述,就是它是有可能将来这个嫩小于他的,但但是呢,嗯,就是也也可能不小于啊,也可能不小于好,那么假如这个情况成立了,我就更新,怎么更新呢?那就微微。
09:14
微微点update,先把我们这一个pre前驱节点更新一把,前驱节点就是结了。那这个就是index,微微还要更新我们这个距离,距离,那这边是截距离,就是认。大家看清楚没有,我把这句话再写一遍啊,有点不好理解,更新更新什么呢?截这个顶点,截这个顶点到前区。啊,前驱。前区为为index这个顶点。哦,那么。呃,当然下一次过后这个顶点就会变化了,这个地方又是什么意思呢?这是更新出发顶点,顶点到截这个顶点的距离。
10:08
就说就说你这个地方,你是首先这个当前这个解没有被访问过,而且你是把这个解考虑进去过后呢,诶你发现现在的距离还变小了,诶这个时候我们要更新这个实际的一个原先记录的这个情况了啊,代码就写完了,就update,就这意思,好,那我我进来过后是不是我先去。更新一把呀,也就现在只要我一更新,你会看到原先的这个整个这个三个数字就变成这个德行了。这就对了,看看是不是这样子的呢?OK,同学们,跟上我的思路,我就试一下了啊,Update。把这个index放进去。放进去,我这里写个注释,这注释叫什么呢?更新index下标。下标。
11:00
顶点index这个就叫index这个顶点吧,顶点啊到到周围。叫小周,诶这个怎么写啊周。周围周围顶点的距离,距离和这个前区前区。前区顶点。先去顶顶,好,这样子我们我们试一下吧,同学们好吧,这个稍微有点绕,但是我们试一下,大家可能一下就明白老师的这个含义是什么意思了。来,走一下。啊,这真他妈不好讲,这玩意儿。好,我先停下来。停下来,我,我在。我先把这个停下来了,我再来给大家跑一下。再给大家debug一下,你们看一下,一下就明白了,好吧,就其实大部分同学应该也知道老师在说什么,但是这个确实很很难描述,就是算法呀,他他这个描述是比较困难的,那同学们看我现在先走一步,先走一步过后同学们可以看到目前这个VV的情况是这样子的,就是我们刚才看到的这个情况。
12:21
是不是这样一个情况。对,是这样子的吧,现在没有没有任何变化,现在呢,我往下面走,走一步,把这个update走一下,走好,那我们走完了过后,同学们看黄色的就是变化的,我们看是不是变化了。Already,啊,这个为什么没有改动过呢?这待会儿这个代码还有点问题啊,应该这个六应该变成一才对。六变成一才对,待会我再看看代码有什么问题,再看地址地是不是不是都改了呀,236535460没问题吧,前区节点是660066也是正确的,但这个地方我们通过第八个发现这个代码有问题,就already现在一个六呢,按理说应该变成一,好我们看看是哪里的问题。
13:07
好,代码有有些小问题我们要调一下。是不是在初始化的时候,哦哦,不好意思,这方应该设为一。因为这是啊,这个这个是零是没问题的,这个是没问题的,呃,这个是没问题的,我看看VZ提的。那就是这个visit的这个地方呢,我们有代码没有去处理,为什么?因为你想这个visit的你没有处理,到时间肯定是要出问题的,对不对,那RR哪个地方来处理呢?我们简单的看一下啊,不着急。看到下边吧,往下面拉一拉。哦,这地方我们少写了一句话,因为你在V初始化的时候,这个index这个地方其实就可以直接怎么处理了呀,就是我们R这个下边为index的地方,我们就直接认为它已经初始化了,也就是说设置设置出发顶点。
14:11
哎,出发顶点被访问过,被访问过唯一。哎,这样就没问题了吧,这样就没问题了,那这个我就不再debug了啊,其实刚才同学们看到debug就是这一点不对嘛,其他都是OK的,好,现在经过一番倒腾呢,其实大家可以看到我们把已经把从这一步到这一步核心代码写完了。而且同学们可以看到,当我们第一次处理完了过后,这个距离我们可以打出来的话,我们如果显示的话,它应该是几个数组的情况就是这样子的。就是这样子的,我们可以呃,打一下给各位同学,嗯,我看看需不需要现在打啊。需不需这个应该待会再打吧,不着急,就说现在你们可以看到,因为从数组可以看出来就是这样子的,对不对,000166006600,而它的地址呢,A点是2346,我们再来确认一下。
15:14
我们再来确认一下啊,不着急,我们确认一下,再debug一下。再提拔一下,就最最核心代码已经写完了,那待会呢,就是再调一调代码就OK,好,同学们往下走。好,我给大家。我给大家运运行一下,但现在在哪呢。好,往往下走一步。我们现在是顶点停在哪的,我看一下在这追进去,追进去下一步再下一步,好,我们来看一下。看一下这三个数组的情况。看一下这三个数组的情况啊好。再来确认一下00001正确第四。二三。65356535460正确正确好。
16:03
呃,前区节点6600660。正确,好,那也也就是说我们现在其实已经确确实实已经完成了这一步到这一步,以及我们最最核心的代码,那么下面的代码呢,就是要去解决怎么去选下一个新的节,新的一个访问顶点,因为你现在相当于我们已经完成了G。这个顶点到它的第一层的所有顶点的访问,但是你还没有去考虑下面,因为下面还有顶点,所以说这边的代码在解决就完成了,其实就是一个方法,怎么去选取下一个新的访问定点作为出发。顶点。呃,在在,呃,作为这个新的访问顶点。啊,当然不是出发点,出发点点G不能变,变化了就是你会选下一个,下一个其实就是A这个地方需要一个方法,第二个呢,要便利所有顶点。
17:02
你不能,你不能说把这个点做做完就就敢保证最低的最小的,其他景点也要变一下,好,那关于这一块功能的实现呢,我们放到下一个视频,我大家讲解,待会呢,大家先把这这一步到这一步好好理解一下。
我来说两句