一个著名的最贪心也最厉害的算法——Dijkstra算法 _Dijkstra算法

在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

文章插图

谈到最短路，对于我来讲最喜欢的算法不过floyd ，无脑，简单，好理解。但是面向oj上边解题的方式来讲， floyd的复杂度常常面对超时的可能，这也使得同样好理解的dijkstra算法更受到青睐。今天咱们就来说说是典型最短路算法——Dijkstra算法

文章插图

Dijkstra算法具体步骤为：（1）初始时， S只包含源点，即S＝， v的距离为0 。U包含除v外的其他顶点， U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。
（2）从U中选取一个距离v最小的顶点k ，把k ，加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。

文章插图

Dijkstra算法代码实现：

文章插图

算法实例：已经带权有向图G如下图所示，现求节点2到节点3的最短路径。这里要求节点ID从0开始并且连续编号，且边的权值大于0 。后面的代码实现也是要遵循这两个前提条件的。
如果两个节点见未直接相连，则节点间的距离设为无穷大，可用一个很大的数表示。

文章插图

图中红色数字表示边的ID ，圆圈中的数字为节点ID ，边旁边的黑色数字表示节点间边的权值。并且所有ID均不重复。
（1）初始时，标记起点2为已访问的节点，并置于集合U中，此时集合U={2} ，集合Y={0,1,3} 。
且初始化其它节点到起点2的距离distance[N]数组， N表示图中节点数。distance[N]数组不仅需要保存其它节点到起点2的距离，也要保存起点2到达该节点的最短路径的最后一个中间节点，这里称为当前节点的前节点。如果没有前一个节点则设为-1 。
此时， distance[N]数组初始化为 {distance[0]={∞,-1}, distance[1]={2,2}, distance[2]={0,-1}, distance[3]={10,2}} 。标粗的表示该节点已经置于集合U中。
（2）在集合Y中找出距离起点2最短的节点，遍历数组distance[N]得节点1距离起点2最近，并将其加入集合U中。此时集合U={2,1} ，集合Y={0,3} 。
（3）以新加入集合U的节点1为中间节点，更新起点2到其它节点之间的最短距离。
对节点0 ，因为节点2到节点0的距离为无穷大∞ ，大于起点2通过节点1到节点0的距离2+3=5 ，并且节点0的前屈节点变为1 ，所以更新distance[0]={5,1};
对节点3 ，同理，因为节点2到节点3的距离为10 ，小于节点2通过节点1到节点3的距离1+∞=∞ ，所以无需更新。
所以，更新完之后的distance[N]取值情况为：{distance[0]={5,1} ， distance[1]={2,2}, distance[2]={0,-1}, distance[3]={10,2}} 。
【一个著名的最贪心也最厉害的算法——Dijkstra算法】（4）重复步骤2 ，继续在集合Y中寻找距离起点2最短的节点，并访问它。遍历数组distance[N]知道节点0到起点2的距离最短为5 ，其节点0加入集合U中。此时集合U={2,1,0} ，集合Y={3} 。
（5）重复步骤3 ，以节点0为中间节点更新集合Y中节点到起点2的距离。因为distance[0].first+matrix[0][3]=5+4=9 ，小于distance[3].first=10 ，所以更新distance[3]={9,0} 。