00:00
好,我们根据刚才的这个思路分析,一步一步的将这个狄杰斯特拉算法来求最短路径,给大家进行一个代码实现,那么同学们首先呢,我们还是新建一个包包。对,新建一个包点什么呢。那就是迪杰斯特拉这块我推过来。把狄杰斯特拉的对应的英文给大家拷贝过来。把大写的D改一下,Finish。没问题吧,同学们好,现在呢,我新建一个类,跟上我的思路。那就叫狄杰斯特了。All。Reason。对吧,DJ斯特拉的算法把主方法给。勾上。没吧,同学们,好的。把这个勾上以后,我们接着往下走,那首先我们第一步是不是还是要先把这个图创建起来,好,我们先来创建一个图。
01:05
没问题吧,Graph这个类,那对于一个图而言,里面有哪些属性呢?我们把它处理一下,比如说唱,它应该可以存放vertex,这个就是存放我们的顶点。顶点数组。下一个。下一个属性是什么呢?就是我们的二维数组,记录我们的这个临界矩阵matrix。没问题吧,这个我们叫做临街。矩阵。非常的简单,那下面呢,我们再来一个属性这个,呃,这两个就是最基本的了,其实现在就已经可以来构建这个图了,是吧,那我写一个构造器。我们一步步来对吧,我们一步一步来构造器,那构造器呢,写个public。
02:02
那你给我传什么样的属性进来呢?非常简单,你这次我们简单一点哈,就直接接收就可以了,比如说你给我传一个ver text。这个髂数组,然后呢,再给我传。一个matrix。Matrix这个临接矩阵就可以了,就可以,那现在我直接接收,这次我们简单一点,就直接你给我,给我过后我就直接拿。直接付给我就行了,好吧,我就不再拷贝复制了,就直接指向就行。就说你给了我一个顶点数组,我直接接收,我也不再拷贝了,同样道理,Matrix呢,也是一样,Matrix。你给我一个matrix好的,我直接接收完事了。现在呢,有了有了这个图过后,我们再来写一个显示图的方法。那显示图的方法呢?我们写个public。
03:02
好吧,Vod show我们的graph。对吧,那怎么去显示呢。我想想歌那非常简单了,一个for循环就可以。我用一个数组把他们的一个连接关系拿到,然后是matrix。Matrix给我了。你把这个ma matrix给我过后呢,我就直接用A工具输出就行。点two string把谁放进去呢?OK,把link放进去就可以,是不是非常简单?好,那这个图我们基本上就写完了,那现在呢,我们来玩一把呗,首先呢,我们先把顶点数组拿到。对。Vertex。等于,等于什么呢?好,我们六一个叉,其实这样可以直接给,是不是,因为它是一位数组嘛,你直接给就行了,比如这里面现在是A。
04:05
B。C。对吧,同学们D。D。Abcde。F。ABCDEF,嗯,别写错了,ABCDEFG,我们一共七个顶点。我们一共七个顶点,格式化一下。那现在有了这七个景点过后呢,我还需要一个临街矩阵。那临接矩阵怎么去处理呢?很简单,咱们写一个就行。好吧,应。二维数组嘛,说白了那就是matrix。Matrix等于你这个地方,我们就六一个这样数组,因为你你这个matrix的大小呢,跟你顶点的个数是有密切关系的,对吧,所以说我们就认识一下,同样下面这一个,它每行列列呢,也是认识就拿到了。
05:07
拿到以后,我们现在呢,再定一个发音的常量N,我们定为65535,跟我刚才一样,就说如果用我们用6535代表它不可连接。对吧,表示表示不可连接。写完,那现在呢,我们就可以把这一个临界矩阵创建好,付给我们这个graph就可以了,那临界矩阵这个过程太麻烦了,就是说我还得一个一个对照这个写,我已经有一个准备,大家看一下就行好吧。其实挺简单的,我这个临界矩阵呢,已经准备好了,我拿过来用,这个大家应该能看懂。就说。呃呃,D零号就是相当是ABCDEFG嘛,然后这边也是就是AB,这就这一行呢,就代表A对应的就是BCDEFG对不对,N代表不可连接好这里就有了,那有了过后我们现在就可以创建。
06:13
创建什么呢?OK,我们可以创建啥呀?同学们,是不是我们就可以创建一个图graph。对象是这样子的同学们六一个。6GRA数,那现在呢,我们直接就把上面的vertex数组和matrix这个二维数组呢付给他,付给他以后我们得到一个变量名就叫官,然后呢,我们测试一下我们输出看看图形对不对,测试看看这个图对不对。看看。图的临接矩阵OK,是否OK非常简单,那就用G。点什么呢?Show graph,我们运行一把。好,那么运行完了后,我们可以看到没有任何问题,对不对,这边是6535了,然后关系也很清晰,就是跟我们这刚才分析的这个是一完全一样的,对不对,就AA这是无穷大的,呃,就是6535的ABA是五,AC是七,看一下。
07:16
AB45 ac471类推好,那也就也就是说现在呢,我们通过一部分代码呢,已然把这一个就是我们对应的图创建起来了,那下面呢,我们就准备来把这个DJ斯特拉需要的一些方法创建好,尤其是哪一个最重要啊,同学们,尤其是这个数组,特别这个类就是v visit的vertex,这个是最重要的。好,那关于这块的这个这个类的编写呢,我们放在下一个视频讲解。
我来说两句