数据结构-拓扑排序和最短路径.ppt

最短路径问题 拓扑排序某个源点到其余各点的最短路径每一对顶点之间的最短路径小结和作业 拓扑排序 一 定义由集合上的一个偏序关系得到集合的全序关系的操作 偏序 自反的 反对称的 传递的全序 R是集合X上的偏序 对于集合X中的任何元素x y 如果都有xRy或者yRx 则称R是全序关系 拓扑排序 偏序就是集合中的部分成员可以比较 全序是集合中的任何成员之间都可以比较 偏序 全序 拓扑排序 按照有向图给出的次序关系 将图中顶点排成一个线性序列 对于有向图中没有限定次序关系的顶点 则可以人为加上任意的次序关系 由此所得顶点的线性序列称之为拓扑有序序列 拓扑排序 用顶点表示活动 弧表示活动间的优先关系的有向图 AOV网 ActivityOnVertexNetWork AOV网中不应该出现有向环 如果存在环 则某项活动以自己为先决条件 拓扑排序 可求得拓扑有序序列 ABCD或ACBD 不能求得它的拓扑有序序列 因为图中存在一个回路 B C D 拓扑排序 拓扑排序 方法1 1 从有向图中选取一个没有前驱的顶点 并输出之 2 从有向图中删去此顶点以及所有以它为尾的弧 3 重复上述两步 直至图空 或者图不空但找不到无前驱的顶点为止 拓扑排序 方法1 a c g b d h f e b h a c d g f e 拓扑序列 在算法中需要用定量的描述替代定性的概念 没有前驱的顶点入度为零的顶点 删除顶点及以它为尾的弧弧头顶点的入度减1 拓扑排序 方法1 StatusToplogicalSort ALGraghG FindInDegree G indegree InitStack S for i 0 i G vexnum i if indegree i push S i count 0 对输出顶点计数while EmptyStack S whileif count G vexnum returnERROR elsereturnOK 拓扑排序 算法 StatusToplogicalSort ALGraghG while EmptyStack S Pop S v count printf v for w FirstAdj v w w NextAdj G v w indegree w 弧头顶点的入度减1if indegree w Push S w for while 拓扑排序 算法 总的时间复杂度 O n e 算法分析 拓扑排序 算法 拓扑排序 方法2 a c g b d h f e b h a c d g f e 拓扑序列 对有向无环图利用深度优先搜索进行拓扑排序 拓扑排序 方法2 b h a c d g f e 此图的一个拓扑序列为 a c g b d h f e 退出DFS函数顺序 e f g d c a h b 拓扑排序 方法2 最先退出DFS函数的顶点是出度为零的顶点 为拓扑排序序列中最后一个顶点 因此 按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑排序序列 结论 拓扑排序 方法2 voidDFS ToplogicalSort GraphG intv 如何确定vfor v 0 v G vexnum v visited v FALSE 访问标志数组初始化InitStack S 存放顶点 按照出DFS的次序for v 0 v G vexnum v if visited v DFS T G v 对尚未访问的顶点调用DFS while Empty S 输出拓扑排序的结果Pop S v printf d v 拓扑排序 方法2 voidDFS T GraphG intv 从顶点v出发 深度优先搜索遍历连通图Gvisited v TRUE for w FirstAdjVex G v w 0 w NextAdjVex G v w if visited w DFS T G w 对v的尚未访问的邻接顶点w递归调用DFS TPush S v 顶点v的DFS函数执行完毕 DFS T 拓扑排序 练习 a c g b d h f e 写出下图的所有的拓扑序列 单源点的最短路径 给定带权有向图G和V0 求从V0到其余各顶点的最短路径 Dijkstra算法 1 按照路径长度递增的次序产生最短路径 将最短路径的终点命名为V1 次之的终点命名为V2 Dijkstra算法 S V0 S V0 V1 S V0 V1 V2 2 用集合S记录下已经求出的顶点 Dijkstra算法 3 用数组D记录V0到S中每个顶点的最短路径的长度S V0 V1 V2 Vm D i 是V0到Vi的长度0 i m 1 长度最短的路径 V0 100 10 10 5 50 V1 V2 V5 V4 60 V3 20 30 Dijkstra算法 2 假设已经求出了V0到V1至Vk 1的最短路径即 S V0 V1 Vk 1 3 求下一条最短路径 终点为Vk 不在S中 V0 Vk 则该路径上的顶点一定都在S中 Dijkstra算法 用反证法 假设存在WSV0 W Vk V0 W中的顶点都在S中 那么 我们就会选择W作为Vk 而不会选择Vk 矛盾 Dijkstra算法 因为V0 W比V0 Vk短 路径的形式一定为 V0 Vi1 Vi2 Vip Vk Dijkstra算法 Vi1 Vi2 Vip S V0到Vk的最短路径是V0到Vip的最短路径 Vip到Vk的边 如何找到Vk Dijkstra算法 min D i dur i k i 0 1 k 1 VkS S V0 D 0 0 S V0 V2 D 1 10 S V0 V2 V4 D 2 30 S V0 V2 V4 V3 D 3 50 S V0 V2 V4 V3 V5 D 4 60 V2 V5 V4 V3 Dijkstra算法 为了减少计算量 改变一下计算次序 初始时 D k 当S S Vj 修改 D K min D k D Vj Dijkstra算法 1 设置初始值 2 从D中选择一个最小值 假设为D k 要求Vk不在S中3 修改不在S中的每个顶点u的最短路径值若D k G arcs k u D u 则D u D k G arcs k u Dijkstra算法 S V0 4 重复2 3 直到所有的顶点都在S中 如何保存V0到V的路径 1 保存V0到V的路径上的顶点 即 不保存边和顶点之间的顺序 2 存储结构 n n的矩阵p Dijkstra算法 3 矩阵的第V行表示V0到V的路径上顶点 如果顶点W在路径上 则p v w TRUE否则 p v w FALSE 初始 如果V与顶点V0邻接 则p v V0 TRUE 其它数矩阵元素的值都是FALSE 当从V0到V的路径是经过V0到W的路径 然后 通过边到达V 则p v p w p v v TRUE Dijkstra算法 Dijkstra算法 FFFFFF V0 V1 V2 V3 V4 V5 V0 V1 V2 V3 V4 V5 FFFFFF TFTFFF FFFFFF TFFFTF TFFFFT 选取V2后 V0到V3的路径经过V2 P V3 P V2 P V3 V3 TRUE TFTFFF TFTTFF Dijkstra算法实现 图 带权的邻接矩阵路径 矩阵距离 数组DS 数组final 如果final v TRUE 则v在S中 voidShortestPath DIJ MGraphG intv0 PathMatrix Dijkstra算法实现 voidShortestPath DIJ MGraphG intv0 PathMatrix v入选 即v0到v的路径最短 Dijkstra算法实现 voidShortestPath DIJ MGraphG intv0 PathMatrix if for void Dijkstra算法实现 15 ab 2 ac 10 ad 2 9 ace 6 acf 6 16 9 10 14 14 acfg adg 课堂练习 Dijkstra算法讨论 2 权值要为正数 否则 得不到正确结果 1 算法的总的时间复杂度 O n2 3 当权值出现负数时 要使用Bellman Flord算法 Dijkstra算法讨论 都是从一个顶点开始 都有一个距离数组D 都有一个顶点是否已经被选取的标志 4 和Prim算法有相似和不同的地方 Prim算法产生的最小生成树67 Dijkstra算法讨论 a b e g f 14 d 8 c 5 18 21 Dijkstra算法产生的支撑树85 19 Dijkstra算法讨论 每一对顶点之间的最短路径 问题 给定一个图G 求出G中任意两个顶点之间的最短路径 距离和经过的顶点 解决方法 对图中的每个结点V 以V为源点 调用Dijkstra算法 时间复杂度为O n3 显然 顶点vi和vj之间的最短路径通过了n个顶点的某些顶点 Floyd算法 首先对顶点进行编号 n个顶点对应1 n个整数 分别叫做V1 V2 Vn 弗洛伊德算法的基本思想是动态规划 Floyd算法 1 求出顶点Vi和Vj不经过任何顶点的最短路径 路径的长度就是二者之间边的权重 表示为 2 当求出后 即Vi到Vj经过V1到Vk 1中的某些顶点的最短路径 则 Vi到Vj的中间经过V1到Vk中某些顶点的最短路径 Floyd算法 Floyd算法 Floyd算法 综合 1 和 2 有 3 当k n时 即就是Vi和Vj之间的最短路径 Floyd算法 1 定义一个n阶方阵D 1 表示初始时 任意两个顶点 i j 之间的距离D 1 i j G arcs i j 由D k 1 生成新的矩阵D k 表示任意2个顶点之间最短路径的长度 中间经过的顶点的编号小于K D k min D k 1 i j D k 1 i k D k 1 k j 2 fork 0ton 3 D n 中存放的是任意两个顶点之间的最短路径 0 4 0 3 D 1 11 6 2 0 0 ab 0 ca ac ba bc 0 P 1 Floyd算法演示 0 ab 0 ca ac ba bc 0 4 3 7 cab D0 P0 Floyd算法演示 11 0 0 6 6 2 0 0 ab 0 ca ac ba bc 0 4 3 7 cab 2 4 abc D1 P1 Floyd算法演示 6 0 0 6 2 0 0 ab 0 ca ac ba bc 0 4 3 7 cab abc 2 3 5 bca D2 P2 Floyd算法演示 采用邻接矩阵存储每对顶点之间的路径长度采用三维数组存储每对顶点之间经过的顶点 Floyd算法实现 voidshortestPath FLOYD MGraphG PathMatrix if for for Floyd算法实现 voidshortestPath FLOYD MGraphG PathMatrixi P v w i P v u i P u w i if forw Floyd算法实现 时间复杂度 O n3 Floyd算法分析 练习 有6个地点 要求在其中一个地方建立一个娱乐中心 要求该地点距其它各地点的最长往返路程最短 相同条件下 总的往返