在日常生活中，如果需要频繁往返于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 )的距离(通过顶点k )短于原始距离(不通过顶点k )，则修正到顶点u的距离值，并对修正后的距离值到顶点k的距离加上边上的权重。

(4)重复步骤)2)和)3)，直到所有顶点都包含在s中。

Dijkstra算法代码实现：

。

求出节点2到节点3的最短路径，如下图所示。这里，要求节点ID从0开始，连续编号，且边缘的权重大于0。后面的代码实现也遵循这两个前提条件。

如果两个节点没有直接连接，则节点之间的距离将设置为无限大，可以用较大的数量表示。

图中的红色数字表示边缘的ID，圆内的数字是节点ID，边缘旁边的黑色数字表示节点之间的边缘权重。另外，所有的ID不重复。

(1)初期时，将起点2标记为访问完毕的节点，放置在集合u中。此时，集合U={2}、集合y={0、1、3}。

另外，初始化从其他节点到起点2的距离distance[N]数组，n表示图中的节点数。在距离[ n ]数组中，不仅存在从其他节点到起点2距离，而且还存在从起点2到该节点最短路径的最后一个中间节点，这里称为当前节点的前一个节点。如果没有上一个节点，则设置为-1。

此时，distance[N]排列为{distance[0]={，-1}，distance [1]={ 2，2 }，distance[N]={0，-1}，distance。

)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 (大于2(3=5，且节点0的前屈节点为1，因此distance [0]={ 5，1 }；

对于节点3，同样，从节点2到节点3的距离为10，小于节点2通过节点1到节点3的距离1 =，因此无需更新。

因此，更新后的距离[ n ]的值为{ distance [0]={ 5，1 }，距离[1]={ 2，2 }，距离[2]={ 0，-1}，距离

)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]=54=9且小于distance[3].first=10，因此更新distance [3]={ 9，0 }。

此时，距离[ n ]取值的是{ distance [0]={ 5，1 }，距离[1]={ 2，2 }，距离[2]={ 0，-1}，距离

(6)重复步骤2，进而在集合y中找出与起点2最近的节点，遍历distance[N]得知节点3最近，将其放入集合u中。此时集合u={ 2，1，0，3 }，集合Y={}。

(7)重复步骤3，以节点3为中间节点更新集合y中节点到起点2的距离，此时发现集合y为空，结束手续。

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

实现代码：

求出所给终点的最短路径：