OR逐次逼近和FLOYD算法.ppt

《OR逐次逼近和FLOYD算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2021/9/81逐次逼近法二、逐次逼近算法本算法可用于网络中带有负权的边时，求指定点V1到网络中任意一点的最短路。基本思路是基于以下事实：如果V1到Vj的路径总是沿该路从V1先到一点Vi，然后再沿边到达Vj，则V1到Vi的这条路也是V1到Vi的最短路。令P1j表示从V1到Vj的最短路长，P1i表示从V1到Vi的最短路长，则必有以下方程：用迭代法解方程：开始时令即用V1与Vj间的直接距离做初始解，若V1与Vj之间无边，那么记+∞第二步起，使用迭代公式：当进行t步，若出现则停止；即为V1到各点的最短路径例题：求下图中V1到各点的最短路径V1V4V7V8V6V3V2V525-

2、347-124-3364解初始条件为：第一轮迭代：第一轮迭代：类似可得：可以看出表示V1两步到Vj的最短路径计算结果：第六列与第五列相同为最后计算结果已知最短路长，若需知道V1到各点的最短路径，可以用“反追踪”的方法。如需求V1到V8的最短路径：已知P18=10，而P18=min{P1i+Li8}，在表中寻求满足等式的Vi点，容易知道P16+L68=10，记下;再考察V6，由于P16=6，而6=0+6=P13+L36，记下;再考察V3，由于P13=0，而0=2+(-2)=P12+L23，记下;再考察V2，由于P12=2，而2=0+2=P11+L

3、12，记下;所以V1到V8的最短路径为v1v2v3v6v8的实际意义为V1到Vj之间至多含有k-1个中间点的最短路权因此在含有n个点的图中，如果不含有总权小于零的回路，求从V1点到任意一点的最短路权，用上诉算法最多经过n-1次必定收敛。如果含有总权小于零的回路，最短路权没有下限。2021/9/810Floyd算法2021/9/811Dijkstra算法是求源点到其它顶点的最短路径。怎样求任意两个顶点之间的最短路径？我们可以把Dijkstra算执行n次，每次从不同的顶点开始，则算法时间复杂度为O（n3）。Floyd弗洛伊德给出了另一个算法，时间复杂度也是O（n3），

4、但是形式上简单些。2021/9/812算法基本思想，2021/9/813算法基本步骤2021/9/814例13：求图中各点之间的最短距离v1v2v3v4v5v10512∞v25010∞2v323028v42∞604v5∞24402021/9/8152021/9/816