183-尚硅谷-图解Java数据结构和算法-Dijkstra算法解决最短路径问题(4)

我们接着写下面的代码，那刚才讲过，我们下面还有一段代码，就是这个。对，就是。要写一个方法，能够继续选择并返回新的访问顶点，那我现在呢，把这个方法写在哪里呢？各位同学，这个方法呢，我们显然是写在。我们写在往下走，写在visited的vertex vertex这里面是最合理的，我就写在这里了，好吧，写在这里。嗯，这个方法的名字咱们这样取名了，Public，返回一个int up。这个版我先写完啊，Update。应该叫update。对，更新一下。那怎么写呢？首先mini我们初始化一个65535。对，再写一个index等于零。

好，那现在呢，我们来进行一个for循环，我把这个。我我把这个写一写啊，就是for循环n ti。等于零，I小于什么呢？I小于已经访问过的这个数组的大小。I加加。I加加，现在呢？我们做一个判断，如果already already，它这个I是等于零的，就表示目前。I，这个顶点还没有被访问过，对不对，并且呢，我们还满足一个什么条件呢？诶还满足你地势。对，第四这个I它小于迷。小于这个mini。也就是说我要我要去，如果我这个mini还小于你大，就是我设置这个mini是大于你这个的，那么我就要进行一个。我就要进一个进行一个一一个修改，或者是更新DS谁呢，就把这个最小值换成真正的最小值，因为你小你DI是小于mini的嘛，所以说我把这个mini呢，就制成你制成这个DI就完了，那做完了以后，这个index呢，就换成I，也就是说我下一个顶点就是。

下一个新的新的这个访问地点就变成index了，好的，那这个时候就其实就返回index就可以了。但是在返回之前呢，我们要更新一下这个顶点被访问过，同时更新更新什么呢？更新这个index，这个顶点被访问过了，明白这意思吧，那我就写上这个了。Index。干什么呢？等于一，那么就写完了，再说一下，这再说一下我们这个方法的一个功能啊，功能就是继续选择并访问新的。

并返回新的访问定点，比如说同学们待会可以去试一下，就是说当我们调用这个方法过后呢，当G访问过后，G点访问过后，我们再去拿一个新的节点，你会发现是I是是这个A，也就是说返回一个零。这段代码就这样写的，就说我我我把这个所有访问的这个数组进行一个遍历，我发现他还没有访问过，并且对应的这个I，这个下边对应的距离还小于这个命令，我就不停的找，不停的找，整个遍历完了过后是不是就找到一个。真正那个还没有访问过的这个节点里面的那个距离最小的，然后把这个应该返回就可以了，就这意思，那有了这个方法功能，上面的代码就比较好写了，来写到这里来。是不是，是不是现在我们就要来完成老师刚才说的这个动作。而且还要便利是不是，那我这就一一步到位啊，同学们看我的代码。朋友看代码，下面的代码呢，应该。

应该怎么写呢？好，Index选取下一个节点了，VI。点update，微微点update这句话我写一下就要干什么呢？选择并返回并。对，并返返回，呃，这个地方。我想一想啊。我想一想，这地方其实没有必要写，直接一个for循环就可以了。for int节。因为你姐从一开始吧。节小于vertex。Vertex。的。呃，看看这个顶点啊，对它的N。对节加加。啊，这样写就对了。从因为你有一个有一个顶点实际上已经被访问过了吗？所以说我就从节等于一开始走开始走，那这个时候我们就拿到这个index了。

对不对，怎么填呢？微微点update。对，这时呢，我们就写上刚才那句话干什么呀，就是选择并。并返回并。返回什么呢，新的。访问。顶点。没问题吧，好，现在呢，我们这做完了以后，是不是又要更新了。因为你你这选择了过后，是不是又继续更新这个index吗？这样就是一个。过程诶，这样就相当于把整个顶点全部走一圈，然后呢，这边再写一下啊，还是把刚才这句话拿过来就行了。这样就做完了。哦，这样就做完了，看看能能否理解啊，能否理解也是，也就是说我们先把第一个顶点走完，走完过后呢，再把剩余的所有顶点一个一个的走一遍就OK了。

走，每走一次呢，选一个新的顶点。选一个新的顶点。呃，出现一个新的这个顶点，再去往下走，就是我这写的就是继续选择并返回新的访问顶点。对的，那做完了后，要把整个这个顶点都变了一次，这个代码就写完了，那写完过后呢，我们现在准备来测一下，看看效果怎么样，嗯，我们怎么来测呢？我再写一个方法能够显示出，就说现在我在写一个方法，能够把我们最后这个结果给看一下，是不是就比较清晰了呀？好，我再写一个方法吧。因为这这段代码走完过后，这这个结果就有了，明白吧，现在呢。我在这儿再写一个方法，能够显示一下。Public。吊箱。显示最后。最后的这个结果没问题吧，同学们，那public void void show。

我们要显示的结果其实就是这三个数组，说白了就三个数组，就把这三个数组，即即将三个三个数组的情况输出一下就可以了，数组的情况输出，其实最后真正的结果是哪一个呢？真正的这个结果其实就是这个。诶，能看到这个效果就OK，明白吧，好，现在呢，我们把它写一下，看看是不是这样子的了。好，我说出一句话。为了好看，打一个格式对不对。打一个分隔符，然后呢，下面呢，我们先输出输出说输出哪个数组呢，先把。Already。先把already already输出一下，诶先把这个输出一下，很简单，后循环anti I等于等于0I。

诶就复习完成钱就完了，好吧，那就是int I。TI。All right。Already。Already。然后呢，我们把这个输出来即即可。好，那就是I，为了好看呢，我这里加一个空格就完事了，好吧，非常简单，这块我们就不换行了。然后紧接着我们在输出什么呢？各位同学，我们在输出它的前驱。顶点是哪些，就最后这一次的啊，最后这一次的，如果你每次都要看你，你都就多掉几次就行了，For循环it，那么还那就把这个复制一份就行。这样子吧，同学们复制完了过后呢，我们这边便利的就应该是play visit的。就完事了。

好吧，最后我们是不是还要输出。我们还要输出哪一个呀，对，我们最后还要输出这个地势。哪一个呢？各位同学，就是这个数组。第十数组来看一下吧。定时数组，那跟上面其实也是很类似的了。粘一下就可以了，I我们这边就是第十数组。好代码就写完，那这边测试完了过后，我们来把来把这个结果看一下，对不对吧。这处理完了过后用graph.show诶这个show方法里面写，那这边我们再写个show方法吧。再写个数，方法就是显示最后结果。显示结果，显示结果呢，我就public VO的show我们的。呃，的确是他拿到一个结果，我们就需要。狄杰斯特拉。好吧，受狄杰斯特拉。

然后呢，这边我们就调用。微微点受就完事了。那这个时候我在这调的时候呢，就用graph。点设DJ斯特拉，好，同学们，我们运行一下，看一下效果怎么样，先不去。呃，先不去这样子了。先不去debug了，Debug先关掉，好，我们运行一把。我们看结果。好，这个结果。因为没有。没有把这个换行，所以说看的非常的麻烦，我把这一个换行输出一下。每处理一次呢，我们换一行对吧，这边我们。输出第十数组的时候呢，我们也换一行，再运行一把。运营官，我们看效果了，哎，同学们看看我们这个结果对不对。呃，所有的节点，所有这节点都反过了1234567好七个节点。搞定，那么我们可以看到它的前驱最后变成这个样子了。

最后呃，就是这个景点G。G到A的距离为二最最短距离啊，G到。记到B的最短距离，3G到这个以此类推，我们看看跟我们最后推出来结果一样是不是一样就可以了。那怎么来判断是不是一样呢？呃。我们来看一下吧。呃，要不这样子，因为这样子看起来太麻烦了，我我把最后这一行稍微的处理一下，让他能够直接写出ABCDEFG，好吧，这样子看起来会轻松一点，我在这稍微的处理吧。来，同学们跟上我的思路，显示的时候稍微处理处理啊，为了好看，为了好看，最后的。最短距离距离我们处理一下，怎么处理一下呢？代码也非常简单，我这样写。

OK，那差的话呢，我们先把整个ver的ver t这个这个顶点先把它得一下。呃，我们就直接写吧。我为了好看啊，我这样写一个数组来处理一下好看。往这接着写，干脆就把这个拿下来吧，OK，待会大家知道我要做什么事情拿下来，拿下来过后呢？我怎么做呢？我先定一个count等于零。没问题吧，然后呢，我负循环，怎么负循环啊，同学们那就是I。第四是不是，哎，第四。第四第式完了过后呢，很简单，我们下面这样处理，如果注意听I，它不等于65356。65535，就是说它确确实实这个地方是有有距离了，我们就处理，因为你如果等于6535，那代表不能连接嘛，是不是好，那就怎么写呢？好的这样写就行了，来同学们这样不要换行了，我就这样写ver。

Pack。这是第几个景点呢？好，Count这个景点。是不是，然后加上它的一个括号，这是个值嘛，那相当于说我在这呢，就加上一个什么呀，加上我们这个I就可以了，因为I是我遍历出来的距离。代码就写完了，如果如果它呃等于6535，那怎么办呢？你就输一个这样的东西就行了，代表是一个无穷大啊N，因为我们这个N就代表是不连接的，当然你这直接输个6535也可以对吧，就是这样为了好看，仅仅是为了好看而已，最后这个负循环结完了，过后这边还没结束的时候，再看看佳佳代表统计下个顶点。

呃，整完了以后再输出一个换行，待会就写完了，来朋友们，我们再看一下效果好不好看了。诶，他们是不是又没有换行啊，在这儿是的，又少一个换行SYH。Sys OK。输出，我们再来运行。好，这样看的应该就比较清晰了，同学们看就说G呢到A是2B CDF到自己呢是零。那么我们来验证一下，嗯，到底对不对我也不知道啊，我们试一下吧，我把这个结果先。拿到我们这边来，因为这也我我我把这个拿过来啊，同学们我们验一下。那怎么知道对还是不对呢？好，这个地方我把结果先拿过来，我们看一看到底对不对，好吧，好，到底对不对，我看一下来，我们用人工的方式验一下G。

接到A最短，呃，确实是二，这个是正确的，接到B1条接到B，这是联通的哈，这个也是正确的接，接到C好C大家看C呢，接到C其实有两条线，一个是这一题。通过这条线过来，还有一条线是通过这条线过来，现在嗯，这个二加七是最最短的，因为二加七不是不拆九吗？你要从这条线走的话，不就变成了12吗？输出到C也是正确的，对吧？那么G，呃，G到DG到D的话是在这。那也有两条线，一个是这这样走。还有一条线是这样走，那短一点的应该是十了，是不是这条线最短说这个就是十，最短距离为十。没有问题吧，同学们，好的，那到E呢，到E当然就一条线过来了，到F呢当然是六，到G自己呢，当然就是零了，好，这个答案是没有问题的，答案是完全正确啊，同学们，完全正确，好同学们，那到现在，到现在我们这段代码就写完了，就写完了，大家看看能否理解啊，能否理解代码呢，就这么写。

代码就这些大家好好的理解哈，其实你要说难点在什么地方呢？就是它太综合了，就他考虑的东西是比较综合的。每个定点我们就一次性的全部算出来了。好吧，同学们，关于这个知识点呢，大家再好好的理解一下，待会我们再做一下整理。