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

作者：咱小二 2018-04-26 08:43:52

在日常生活中，我们如果需要常常往返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}}。

（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}。

此时distance[N]取值情况为：{distance[0]={5,1}， distance[1]={2,2}, distance[2]={0,-1}, distance[3]={9,0}}。

（6）重复步骤2，再集合Y中找出距离起点2最近的节点，遍历distance[N]可知节点3距离最近，并将其纳入集合U中。此时集合U={2,1,0,3}，集合Y={}。

（7）重复步骤3，以节点3为中间节点更新集合Y中节点到起点2的距离，此时发现集合Y为空，过程结束。

最后我们获得了加入集合U的所有节点，因为没有节点都记录了自己的前驱节点，所以可以获得从起点到任意目的节点见的最短路径。

实现代码：

求给定终点的最短路径：