图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 这里是一则小广告： 关注作者请点击这里哦 ：zdr0
我的专栏里面不仅有学习笔记，也有一些科普文章，相信我的专栏不会让您失望哦～大家可以关注一下 ：数学及自然科学
记得点赞加收藏哦～ 创作不易，请赞赏一下支持一下作者吧[期待]～ 文章中如果有错误的话还请各位大佬多多斧正，感谢！ -尽力写最好的讲义，尽力写最好的科普。 Dijkstra 算法 ，是由荷兰计算机科学家 Edsger Wybe Dijkstra 在1956年发现的算法，戴克斯特拉算法使用类似广度优先搜索的方法解决
赋权图的单源最短路径问题 。Dijkstra 算法原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。需要注意的是绝大多数的Dijkstra 算法不能有效处理带有
负权边 的图。
下面，我们就从一个赋权的有向图为例开始解释Dijkstra 算法。
设一个赋权有向图
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。其中的每条边
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的权值为一个非负的实数
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，
该权值表示从顶点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到顶点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的距离 。并设一单源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。现在我们的任务是：找出从源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 出发，到
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中所有的节点的最短路径。
我们来看一个具体的例子：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 图片1：例图。
这是一个具有
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 个顶点的赋权有向图，其顶点集合为
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，其权值分别为：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 现在我们选定
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 为原点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 图片2：选择v_1作为原点s。
则从源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 出发，到
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中所有顶点的最短路径分别为：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 图片3：V中的源点s(v_1)到V中其余点的最短路径。
即：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 其中，
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 表示从源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 出发，到
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径。
注： 最短路径可以理解为所有可能的路径中总权和最小的那一条路径 。举一个再简单不过的例子：你开车从城市 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到城市 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，假设有很多条路可以走，最短的那条路就是最短路径，总权和可以理解为总的公里数。
以上是我们通过观察和计算比对出来的最短路径，下面我们就来看看Dijkstra 算法是如何帮助我们找到这些所有的最短路径的。
在开始之前，有几个概念需要明确一下。
- 定义一个集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，如果集合 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的某个顶点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 在集合 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中了，那么就说明从源点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到顶点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径已经被找到，而在算法一开始的时候，集合 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中只有源点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。即：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 而且，当且仅当
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的时候算法执行完毕。此时顶点集
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的所有元素都被放进了集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 种，也就是说除了源点以外的所有从源点出发到其余所有顶点的最短路径已被找到。
注：当然了，你也可以认为源点到自己本身的最短路径也被找到了。对于任意一个 无自环的 源点，它到自己本身的最短路径都是 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。
- 下面这个概念可能稍微有些抽象，不过没有关系，这里理解不了的话我们一会讲例子的时候会进行具体说明。这个概念叫做 从源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到顶点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 （一开始 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ） 的相对于集合 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径 。 即从源点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到顶点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的路径 中间 只能经过已经包含在集合 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的顶点，而不能经过其余的还未在集合 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的顶点。而这个相对于集合 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径的长度我们记作：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 而我们之前的
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 表示的是
全局的 从源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径，这个最短路径没有限制“必须在路径中间只能经过已经包含在集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的顶点”，这个全局的最短路径才是我们要的最终解。所以，一般有关系：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 而我们的Dijkstra 算法要做的就是通过不断计算
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 进而不断的扩充集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，当集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 不断被扩充的时候，相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径会越来越短，直到
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 入集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 之时，此时我们便得到了
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，且此时有
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。下面我们来看看算法的设计思想：
输入 ：赋权有向图 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。 输出 ：从源点 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到所有的 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径。 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 初始 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ； 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 对于 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，计算 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ； 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 选择 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，并将这个 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 放进集合 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中，更新 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的顶点的 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 值； 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 重复 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，直到 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。
然后是Dijkstra 算法的伪码：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 下面我们来解释一下这个伪码：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 算法初始，将选择的源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 放进集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中；
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 无自环的源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到自己的最短路径为
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ；
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 当顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 不在集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中时（此时集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中仍只有源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ），开始进入循环；
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 将源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 与点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 之间的权值赋给
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。由于是有向图，所以当源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 不指向任何其他集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 外的顶点时，
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。可以理解为
此时 从源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 出发，
暂时 是达到不了
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的。不过后来随着集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的扩充，从源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 出发一定能到达所有的顶点。一会我们讲解例子时会出现这种情况。此时第一个
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环结束。
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 如果集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 不是空集，则进入循环；
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 选出经过第一个
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环之后的，在集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的，且相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径中距离最短的那个顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ;
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 将这个顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 并入集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，从而达到扩充集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的目的；
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 将顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 并入集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 之后可能会对其他顶点相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路的长度会有影响，所以进入内
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环对有影响的进行更新；
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 即如果从源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到我们在第
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 步选出的顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径的长度再加上顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 之间的距离
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 还要小于源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径的长度还要短的话；
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 则将源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径更新成源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到我们在第
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 步选出的顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径再加上顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 到顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 之间的权值
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。
下面我们开始讲例子，我们还是以图片1中的赋权有向图进行说明。
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 图片4
首先我们还是选择
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 为原点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，那么在算法的开始，
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。之后我们计算除了
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 以外的其余顶点到
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的距离
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，即寻找所有的除了
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 以外的所有顶点相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路，即从
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 出发，到达所有顶点且只允许通过顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 （因为此时集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中只有
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 这一个元素）的最短路径。这是我们的算法中的第一个
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环在做的事情。这时候我们发现想要
只通过 顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 而到达顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 都是不可能的，所以我们有：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 而
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 就是算法中所说的暂时到达不了的顶点了。现在算法的前四步已经结束了，现在开始第五步检验集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 是否是空集，这里显然不是，这里：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 现在进行第六步。第六步是选出经过第一个
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环之后的，在集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的，且相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径中距离最短的那个顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。那我们看看在式
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中那个顶点距离源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 最短就好了，显然是
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，所以，我们这里选择的
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。
那么第七步就是将
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 放进集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中了。此时集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。这就是说明从源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 出发，到顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径已经被找到了。
下面我用绿色表示被放入集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中的顶点：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 图片5：顶点v_6被加进集合S中。
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的颜色我就不变了，因为它一直都在集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中。此时：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 这就说明下次在找相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径的时候
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中就有两个点可以被通过了，这样也许就会使得一些原来到达不了的顶点由于可以多经过一个点而到达，这也就是算法中所说的当我将一个新的顶点并入集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 之后，其他的在集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 以外的顶点的相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径的长度可能会发生改变，因为有些原来暂时到达不了的顶点现在可以到达了。具体的来讲，我们有：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 这个更新步骤我也来详细是说一下，这是算法第八到第十步所做的事情。比如
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，一开始在集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中只有源点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，而找到
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径只能通过顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，这样我们在式
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中所得到
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。但是当顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 也进入到集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 之后我们再找
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径时就可以先通过顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 然后到顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，最后再到
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。现在这两种走法都可以，但是算法究竟选择哪种算法还是要判断哪种走法距离最短，即比较 ：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 之间的大小关系，谁小算法就选择谁。经过比较发现：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 所以选择后者。再比如原来达到不了的
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，现在由于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中多了顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 变得可以达到了，即：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 所以算法肯定选择后者。不过此时算法也没得可选，先要到达顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 就必须走这条路。
其余发生变化的顶点分析类似，大家可以自己试试。
现在算法从头到尾被执行了一遍了，然后我们回到第五步判断
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环的条件还是否为真，此时：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 所以再执行
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环，由第六步从式
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中选择出属于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，且相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径中距离最短的那个顶点为
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，所以，这里我们选择的
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。然后第七步 将
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 放进集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。此时，集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 图片6：v_5被放进集合S中。
此时我们有：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 可见这次没有发生更新，且此时的：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 所以再执行
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环，由第六步从式
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中选择出属于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，且相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径中距离最短的那个顶点为
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，所以，这里我们选择的
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。然后第七步 将
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 放进集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。此时，集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 图片7：v_2被放进集合S中。
此时我们有：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 可见这次在顶点
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 处发生了更新（至于为什么
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 大家可以自己分析一下试试），且此时的：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 所以再执行
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环，由第六步从式
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中选择出属于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，且相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径中距离最短的那个顶点为
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，所以，这里我们选择的
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。然后第七步 将
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 放进集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。此时，集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 图片8：v_4被放进集合S中。
此时我们有：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 可见这次并未发生更新，且此时的：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 所以再执行
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环，由第六步从式
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中选择出属于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，且相对于集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的最短路径中距离最短的那个顶点为
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ，所以，这里我们选择的
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 （至剩下
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 可以被选择了）。然后第七步 将
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 放进集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。此时，集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 ：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 图片9：v_4被放进集合S中。
此时我们有：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 这是最后一次了，且这次并未发生更新，且此时的：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 则不满足算法中的
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 循环的条件，循环结束，算法结束。显然，此时有
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。
最后我们来看一看Dijkstra 算法的时间复杂度。
Dijkstra 算法的时间复杂度是
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。其中：
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 分别为赋权有向图中的顶点个数和边的个数。Dijkstra 算法的时间复杂度是
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 是因为算法总共进行
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 步，每一步选出一个具有最小
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 值的顶点放入集合
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 中，需要
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 的时间。
而选择基于堆实现的优先队列数据结构，可将Dijkstra 算法的时间复杂度降为
图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 。
参考： 图的最短路径算法代码_[最短路径问题]—Dijkstra 算法最详解 屈婉玲教授——《算法》课程。
