文档介绍：—— Dijkstra 算法一、应用背景一、应用背景( (1 1 )应用背景)应用背景——管道铺设、线路安排、厂区布局、设备更新、网络拓扑等。( (2 2) )现实生活中的网络拓扑,可以抽象成由节点( 路由器) 和边(路由器之间的链路)构成的有向连通图,链路的代价可以抽象成边的权函数。之所以称图为有向图,是因为同一条链路(边)不同方向的权值可能不一样。“单源最短路径”问题: ?已知一个有 n 个节点(V0..n) 构成的有向连通图 G= (V,E ),以及图中边的权函数 C (E) ,其中 V代表节点集合, E 表示所有边的集合,并假设所有权非负,求由 G 中指定节点 V0 到其他各个节点的最短路径。?Dijkstra 算法是很经典的求解上述问题的算法, 其基本想法是设计一种最短路径树的构造方法, 按非降次序逐条构造从 V0到各个节点的最短路径. 二、最短路算法二、最短路算法 1 1. .D D氏标号法( 氏标号法( Dijkstra Dijkstra );边权非负);边权非负 2. 2. 列表法(福德法);有负权,无负回路列表法(福德法);有负权,无负回路 4v 1v 2v 3v 4v 6 v 5v 7 225 61 413 4 12 1 1. .D D氏标号法( 氏标号法( Dijkstra Dijkstra ) ) ( (1 1 )求解思路)求解思路——从始点出发,逐步顺序地向外探寻,每向外延伸一步都要求是最短的。最短的。( (2 2)使用条件)使用条件——网络中所有的弧权均非负非负,即。( (3 3)选用符号的意义)选用符号的意义: ①P标号( Permanent 固定/永久性标号) ——从始点到该标号点的最短路权②T标号( Temporary 临时性标号) ——从始点到该标号点的最短路权上界上界( (4 4) )计算步骤及例子: 计算步骤及例子: 0)( 1?vp 第一步:给起始点 v 1标上固定标号 , 其余各点标临时性标号 T(v j )=?, j?1; = l 1j jv s jv第二步:考虑满足如下条件的所有点①与v 1相邻的点,即 ; ②具有 T 标号,即,为T标号点集. 修改的T 标号为,并将结果仍记为 T(v j)。 sv j? jv})( ),( min{ 11jjlvpvT??若网络图中已无满足此条件的 T标号点,停止计算。第三步:令 , 然后将的 T 标号改成 P 标号,转入第二步。此时, 要注意将第二步中的改为。 1v 0jv 0jv )}({ min )( 0jsv jvTvT j??通俗易懂的步骤: ?(1) 初始时, S 只包含起点 s;U 包含除 s 外的其他顶点,且 U 中顶点的距离为" 起点 s 到该顶点的距离"[ 例如, U 中顶点 v 的距离为(s,v) 的长度,然后 s和v不相邻,则 v 的距离为∞。?(2) 从U 中选出" 距离最短的顶点 k" ,并将顶点 k 加入到 S 中;同时,从 U中移除顶点 k。?(3) 更新 U 中各个顶点到起点 s 的距离。之所以更新 U 中顶点的距离,是由于上一步中确定了 k 是求出最短路径的顶点,从而可以利用 k 来更新其它顶点的距离;例如, (s,v) 的距离可能大于(s,k)+(k,v) 的距离。?(4) 重复步骤(2) 和(3) ,直到遍历完所有顶点。 237 18 45 6 6 134 10 52 7 5934 68 2求从 1到8的最短路径