算法最短路径弗洛伊德(算法ppt课件.ppt

1 1 问题的提出 已知一个各边权值均大于0的带权有向图 对每一对顶点vi vj 要求求出vi与vj之间的最短路径和最短路径长度 2 解决办法方法一 每次以一个顶点为源点 重复执行Dijkstra算法n次 T n O n 方法二 弗洛伊德 Floyd 算法 2 求最短路径步骤初始时设置一个n阶方阵 令其对角线元素为0 若存在弧 则对应元素为权值 否则为 逐步试着在原直接路径中增加中间顶点 若加入中间点后路径变短 则修改之 否则 维持原值所有顶点试探完毕 算法结束 3 Floyd算法思想 逐个顶点试探法 从图的带权邻接矩阵G arcs出发 假设求顶点Vi到Vj的最短路径 如果从Vi到Vj有弧 则从Vi到Vj存在一条长度为G arcs i j 的路径 但该路径是否一定是最短路径 还需要进行n次试探 1 第一次 判别 Vi V0 和 V0 Vj 即判别 Vi V0 Vj 是否存在 若存在 则比较 Vi Vj 和 Vi V0 Vj 的长度 取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径 2 第二次 再加一个顶点V1 如果 Vi V1 和 V1 Vj 分别是当前找到的中间顶点序号不大于0的最短路径 那么 Vi V1 Vj 就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径 将它和已经得到的从Vi到Vj之间顶点序号不大于0的最短路径相比较 取较短者为从Vi到Vj的中间顶点序号不大于1的最短路径 3 第三次 再加一个顶点V2 继续进行试探 D 1 D 1 为有向网的邻接矩阵第一步 以D 1 为基础 以V0为中间顶点 求从Vi到Vj的最短路径 该路径或者为从Vi到Vj的边 或者为 Vi V0 V0 Vj D 0 i j min D 1 i j D 1 i 0 D 1 0 j D 0 i j 为从Vi到Vj的中间顶点序号不大于0的最短路径长度 以D 0 为基础 以V1为中间顶点 求从Vi 到Vj的最短路径 该路径或者为从Vi到Vj的边 或者为从Vi开始通过V0或V1到达Vj的最短路径 D 1 i j min D 0 i j D 0 i 1 D 0 1 j 以D 1 为基础 以V2为中间顶点 求从Vi 到Vj的最短路径 或者为从Vi到Vj的边 或者为从Vi开始通过V0 V1 V2到达Vj的最短路径 D 2 i j min D 1 i j D 1 i 2 D 1 2 j 以D 2 为基础 以V3为中间顶点 求从Vi 到Vj的最短路径 或者为从Vi到Vj的边 或者为从Vi开始通过V0 V1 V2 V3到达Vj的最短路径 D 3 i j min D 2 i j D 2 i 3 D 2 3 j D 3 i j 即为从Vi到Vj的最短路径长度 9 例题 10 11 4 论点 A 1 i j 是从顶点vi到vj 中间顶点是v1的最短路径的长度 A k i j 是从顶点vi到vj 中间顶点的序号不大于k的最短路径的长度 A n 1 i j 是从顶点vi到vj的最短路径长度 证明 归纳证明 始归纳于s 上角标 1 归纳基础 当s 1时 A 1 i j Edge i j vi到vj 不经过任何顶点的边 是最短路径 2 归纳假设 当s k时 A s i j 是从顶点vi到vj 中间顶点的序号不大于s的最短路径的长度 3 当s k时 12 i j k A k 1 i k A k 1 k j A k 1 i j 因为 A k i j min A k 1 i j A k 1 i k A k 1 k j 由归纳假设知 A k 1 i j 是i到j的最短路径 标号不高于k 1 A k 1 i k 是i到k的最短路径 标号不高于k 1 A k 1 k j 是k到j的最短路径 标号不高于k 1 所以 A k i j 是i到j的最短路径 标号不高于k 13 图用邻接矩阵存储edge 存放最短路径长度path i j 是从Vi到Vj的最短路径上Vj前一顶点序号 5 算法实现 voidfloyd for inti 0 i n i 矩阵dist与path初始化for intj 0 j n j 置A 1 dist i j Edge i j path i j 1 初始不经过任何顶点for intk 0 k n k 产生dist k 及path k for i 0 i n i for j 0 j n j if dist i k dist k j dist i j dist i j dist i k dist k j path i j k 缩短路径 绕过k到j floyd 14 6 算法分析 设最内层循环体为基本操作 算法有三层循环 每层循环n次 所以T n O n3 15 16 以Path 3 为例 对最短路径的读法加以说明 从A 3 知 顶点1到0的最短路径长度为a 1 0 1