OR 逐次逼近 和 FLOYD 算法教材课程.ppt

2018-4-12 1 逐次逼近法 二、逐次逼近算法 本算法可用于网络中带有负权的边时，求指定点 V1到网络中任意一点的最短路。 基本思路是基于以下事实：如果V1到Vj的路径总是沿该路从V1先到一点Vi，然后再沿边Vi,Vj到达Vj，则V1到Vi的这条路也是V1到Vi的最短路。 令P1j表示从V1到Vj的最短路长，P1i表示从V1到Vi的最短路长，则必有以下方程： 用迭代法解方程： 开始时令 即用V1与Vj间的直接距离做初始解，若V1与Vj之间无边，那么记+∞ 第二步起，使用迭代公式： 当进行t步，若出现 则停止； 即为V1到各点的最短路径 例题：求下图中V1到各点的最短路径 V1 V4 V7 V8 V6 V3 V2 V5 2 5 -3 4 7 -1 2 4 -3 3 6 4 解 初始条件为： 第一轮迭代： 第一轮迭代： 类似可得： 可以看出 表示V1两步到Vj的最短路径 计算结果： 第六列与第五列相同为最后计算结果 已知最短路长，若需知道V1到各点的最短路径，可以用“反追踪”的方法。 如需求V1到V8的最短路径： 已知P18=10，而P18=min{P1i+Li8}，在表中寻求满足等式的Vi点，容易知道P16+L68=10，记下V6,V8; 再考察V6，由于P16=6，而6=0+6=P13+L36，记下V3,V6; 再考察V3，由于P13=0，而0=2+(-2)=P12+L23，记下V2,V3; 再考察V2，由于P12=2，而2=0+2=P11+L12，记下V1,V2; 所以V1到V8的最短路径为v1  v2  v3  v6  v8 2018-4-12 10 Floyd算法 2018-4-12 11 Dijkstra算法是求源点到其它顶点的最短路径。怎样求任意两个顶点之间的最短路径？我们可以把Dijkstra算执行n次，每次从不同的顶点开始，则算法时间复杂度为O（n3）。 Floyd弗洛伊德给出了另一个算法，时间复杂度也是O（n3），但是形式上简单些。 2018-4-12 12 算法基本思想 ， 2018-4-12 13 算法基本步骤 2018-4-12 14 例13：求图中各点之间的最短距离 v1 v2 v3 v4 v5 v1 0 5 1 2 ∞ v2 5 0 10 ∞ 2 v3 2 3 0 2 8 v4 2 ∞ 6 0 4 v5 ∞ 2 4 4 0 2018-4-12 15 2018-4-12 16