在日常生活中,我们如果需要常常往返A地区和B地区之间,我们最希望知道的可能是从A地区到B地区间的众多路径中,那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。
谈到最短路,对于我来讲最喜欢的算法不过floyd,无脑,简单,好理解。但是面向oj上边解题的方式来讲,floyd的复杂度常常面对超时的可能,这也使得同样好理解的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中。
已经带权有向图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的所有节点,因为没有节点都记录了自己的前驱节点,所以可以获得从起点到任意目的节点见的最短路径。
实现代码:
求给定终点的最短路径:
联系客服