《弗洛伊德及其算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《弗洛伊德及其算法ppt课件.ppt（11页珍藏版）》请在金锄头文库上搜索。
1、关于罗伯特 弗洛伊德 RobertW Floyd 1936 2001 计算机科学家 前后断言法的创始人 堆排序算法和Floyd Warshall算法的创始人之一 1 1978年获得图灵奖 斯坦福大学计算机科学系教授罗伯特 弗洛伊德是一位 自学成才的计算机科学家 2 1953年在芝加哥大学获得文学学士学位 1958年获得理学学士学位 1956年他离开西屋电气公司 到芝加哥的装甲研究基金会 ArmourResearchFoundation 开始还是当操作员 后来就当了程序员 3 1965年他应聘成为卡内基 梅隆大学的副教授 3年后转至斯坦福大学 1970年被聘任为教授 1962年他被马萨诸塞州的C
2、omputerAssociates公司聘为分析员 此时与Warsall合作发布Floyed Warshall算法 4 Floyd算法又称为弗洛伊德算法 插点法 是一种用于寻找给定的加权图中顶点间最短路径的算法 1 Floyd算法介绍 该算法名称以创始人之一罗伯特 弗洛伊德命名 5 通过一个图的权值矩阵求出它的每两点间的最短路径矩阵 2 Floyd算法核心思路 从图的带权邻接矩阵A a i j n n开始 递归地进行n次更新 即由矩阵D 0 A 按一个公式 构造出矩阵D 1 又用同样地公式由D 1 构造出D 2 最后又用同样的公式由D n 1 构造出矩阵D n 6 采用的是 松弛技术 对在i和j
3、之间的所有其他点进行一次松弛 所以时间复杂度为O n 3 矩阵D n 的i行j列元素便是i号顶点到j号顶点的最短路径长度 称D n 为图的距离矩阵 同时还可引入一个后继节点矩阵path来记录两点间的最短路径 2 Floyd算法核心思路 7 1 从任意一条单边路径开始 所有两点之间的距离是边的权 如果两点之间没有边相连 则权为无穷大 3 Floyd算法过程 2 对于每一对顶点u和v 看看是否存在一个顶点w使得从u到w再到v比已知的路径更短 如果是更新它 比如 要寻找从V5到V1的路径 根据D 假如D 5 1 3则说明从V5到V1经过V3 路径为 V5 V3 V1 如果D 5 3 3 说明V5与V
4、3直接相连 如果D 3 1 1 说明V3与V1直接相连 8 把图用邻接矩阵G表示出来 如果从Vi到Vj有路可达 则G i j d d表示该路的长度 否则G i j 无穷大 把各个顶点插入图中 比较插点后的距离与原来的距离 G i j min G i j G i k G k j 如果G i j 的值变小 则D i j k 定义一个矩阵D用来记录所插入点的信息 D i j 表示从Vi到Vj需要经过的点 初始化D i j j 在G中包含有两点之间最短道路的信息 而在D中则包含了最短通路径的信息 9 时间复杂度 O n 3 4 Floyd算法过程时间复杂度与空间复杂度 空间复杂度 O n 2 10 Floyd算法适用于APSP AllPairsShortestPaths 是一种动态规划算法 稠密图效果最佳 边权可正可负 此算法简单有效 由于三重循环结构紧凑 对于稠密图 效率要高于执行 V 次Dijkstra算法 5 Floyd算法优缺点分析 优点 容易理解 可以算出任意两个节点之间的最短距离 代码编写简单 缺点 时间复杂度比较高 不适合计算大量数据 11
