Dijkstra算法-寻找有向图中最短路径.doc

Dijkstra 算法- 寻找有向图中最短路径 Dijkstra 算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离。 Dijkstra 算法可以用来找到两个城市之间的最短路径。 Dijkstr a算法的输入包含了一个有权重的有向图G,以及G中的一个来源顶点S。我们以 V表示 G中所有顶点的集合。图中的每一个边,都是两个顶点所形成的有序元素对。(u,v)表示从顶点 u到v有路径相连。假设 E为所有边的集合,而边的权重则由权重函数 w:E→[0, ∞]定义。因此, w(u,v)就是从顶点 u到顶点v的非负花费值(cost) 。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值,就是该路径上所有边的花费值总和。已知有 V中有顶点 s及 t,Dijkstra 算法可以找到 s到t的最低花费路径(. 最短路径)。这个算法也可以在一个图中,找到从一个顶点 s到任何其他顶点的最短路径。算法描述这个算法是通过为每个顶点 v保留目前为止所找到的从 s到v的最短路径来工作的。初始时,源点 s的路径长度值被赋为 0(d[s] =0), 同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于 V中所有顶点 v除s外d[v] =∞)。当算法结束时, d[v] 中储存的便是从 s到v 的最短路径,或者是无穷大(如果路径不存在的话)。 Dijstra 算法的基础操作是边的拓展:如果存在一条从 u到v的边,那么从s到v的最短路径可以通过将边(u,v)添加到 s到u的尾部来拓展。这条路径的长度是 d[u]+w(u,v) 。如果这个值比目前已知的 d[v] 的值要小,我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直执行到所有的 d[v] 都代表从 s到 v最短路径的花费。这个算法经过适当的组织因而当 d[u] 达到它最终的值的时候,每条边(u,v)都只被拓展一次。算法维护两个顶点集 S和Q。集合 S保留了我们已知的所有 d[v] 的值已经是最短路径的值顶点,而集合 Q则保留其他所有顶点。集合 S初始状态为空,而后每一步都有一个顶点从 Q移动到 S。这个被选择的顶点是 Q中拥有最小的 d[u] 值的顶点。当一个顶点 u从Q中转移到了 S中,算法对每条外接边(u,v) 进行拓展。算法思想设S为最短距离已确定的顶点集(看作红点集),V-S 是最短距离尚未确定的顶点集(看作蓝点集)。①初始化初始化时,只有源点 s的最短距离是已知的(SD(s)=0) ,故红点集 S={s} ,蓝点集为空。②重复以下工作,按路径长度递增次序产生各顶点最短路径在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证按路径权重递增的次序来产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点,或者所有蓝点已扩充到红点集时, s到所有顶点的最短路径就求出来了。注意: ①若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。②从源点 s到终点 v的最短路径简称为 v的最短路径; s到v的最短路径长度简称为 v的最短距离,并记为 SD(v) 。(3)在蓝点集中选择一个最短距离最小的蓝点 k来扩充红点集根据按长度递增序产生最短路径的