拓扑排序-关键路径-最短路径.ppt

有向无环图及其应用 要点 拓扑排序关键路径 有向无环图 一个无环的有向图 简称DAG图 DAG图 描述含有公共子式的表达式及工程或系统的进行过程时的有效工具 活动 一个较大的工程被划分成许多子工程 这些子工程被称作活动 活动之间 存在某种约束 如 某些子工程的开始必须在另外一些子工程完成之后 关心问题 1 工程能否顺利进行2 估算整个工程完成所必须的最短时间 有向无环图及其应用拓扑排序问题提出 学生选修课程问题顶点 表示课程有向弧 表示先决条件 若课程i是j的先决条件 则图中有弧学生应按怎样的顺序学习这些课程 才能无矛盾 顺利地完成学业 拓扑排序定义AOV网 用顶点表示活动 用弧表示活动间优先关系的有向图称为顶点表示活动的网 ActivityOnVertexnetwork 简称AOV网若是图中有向边 则vi是vj的直接前驱 vj是vi的直接后继AOV网中不允许有回路 这意味着某项活动以自己为先决条件 拓扑排序 把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 检测AOV网中是否存在环方法 对有向图构造其顶点的拓扑有序序列 若网中所有顶点都在它的拓扑有序序列中 则该AOV网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步 直至全部顶点均已输出 或者当图中不存在无前驱的顶点为止 拓扑序列 C1 C2 C3 C4 C5 C7 C9 C10 C11 C6 C12 C8或 C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C8 一个AOV网的拓扑序列不是唯一的 算法实现以邻接表作存储结构设置一个包含n个元素的一维数组indegree 保存AOV网中每个顶点的入度值 把邻接表中所有入度为0的顶点进栈栈非空时 输出栈顶元素Vj并退栈 在邻接表中查找Vj的直接后继Vk 把Vk的入度减1 即indegree k 1 若Vk的入度为0则进栈重复上述操作直至栈空为止 若栈空时输出的顶点个数不是n 则有向图有环 否则 拓扑排序完毕 算法描述 1 6 输出序列 6 输出序列 6 输出序列 6 输出序列 6 输出序列 6 输出序列 6 输出序列 61 输出序列 61 输出序列 61 4 输出序列 61 4 输出序列 61 4 输出序列 61 4 3 输出序列 61 4 3 输出序列 61 4 3 输出序列 61 4 3 输出序列 61 4 3 输出序列 613 4 3 输出序列 613 4 输出序列 613 4 输出序列 613 4 输出序列 613 4 2 输出序列 613 4 2 输出序列 613 4 2 输出序列 6132 4 2 输出序列 6132 4 输出序列 61324 4 输出序列 61324 输出序列 61324 5 输出序列 61324 5 输出序列 613245 5 输出序列 613245 算法分析 建邻接表 T n O e 搜索入度为0的顶点的时间 T n O n 拓扑排序 T n O n e 关键路径问题提出 把工程计划表示为有向图 用顶点表示事件 弧表示活动 每个事件表示在它之前的活动已完成 在它之后的活动可以开始 例设一个工程有11项活动 9个事件事件V1 表示整个工程开始事件V9 表示整个工程结束问题 1 完成整项工程至少需要多少时间 2 哪些活动是影响工程进度的关键 定义AOE网 ActivityOnEdge 也叫边表示活动的网 AOE网是一个带权的有向无环图 其中顶点表示事件 弧表示活动 权表示活动持续时间路径长度 路径上各活动持续时间之和关键路径 路径长度最长的路径叫 Ve j 表示事件Vj的最早发生时间Vl j 表示事件Vj的最迟发生时间e i 表示活动ai的最早开始时间l i 表示活动ai的最迟开始时间l i e i 表示完成活动ai的时间余量关键活动 关键路径上的活动叫 即l i e i 的活动 问题分析如何找e i l i 的关键活动 设活动ai用弧表示 其持续时间记为 dut 则有 1 e i Ve j 2 l i Vl k dut 如何求Ve j 和Vl j 1 从Ve 1 0开始递推 2 从Vl n Ve n 开始递推 求关键路径步骤求Ve i 求Vl j 求e i 求l i 计算l i e i V1V2V3V4V5V6V7V8V9 064577161418 0668710161418 a1a2a3a4a5a6a7a8a9a10a11 算法实现以邻接表作存储结构从源点V1出发 令Ve 1 0 按拓扑序列求各顶点的Ve i 从汇点Vn出发 令Vl n Ve n 按逆拓扑序列求其余各顶点的Vl i 根据各顶点的Ve和Vl值 计算每条弧的e i 和l i 找出e i l i 的关键活动 算法描述1 输入顶点和弧信息 建立其邻接表计算每个顶点的入度2 对其进行拓扑排序2 1 排序过程中求顶点的Ve i 2 2 将得到的拓扑序列进栈3 按逆拓扑序列求顶点的Vl i 4 计算每条弧的e i 和l i 找出e i l i 的关键活动 StatusTopologicalOrder ALGraphG Stack TopologicalOrder StatusCriticalPath ALGraphG 算法7 14 G为有向网 输出G的各项关键活动 StackT inta j k el ee dut chartag ArcNode p if TopologicalOrder G T returnERROR for a 0 anextarc k p adjvex dut p info dutif vl k dutnextarc k p adjvex dut p info ee ve j el vl k dut tag ee el printf j k dut ee el tag 输出关键活动 returnOK CriticalPath 对图示的AOE网络 计算各活动弧的e ai 和l ai 的函数值 各事件 顶点 的ve Vj 和vl Vj 的函数值 列出各条关键路径 最短路径 所谓最短路径问题是指 如果从图中某一顶点 称为源点 出发到达另一顶点 称为终点 的路径可能不止一条 如何找到一条路径使得沿此路径上各边的权值总和达到最小 1 单源点最短路径2 所有顶点对之间的最短路径 单源点最短路径 给定带权有向图G和源点v 求从v到G中其余各顶点的最短路径 V5 V0 V2 V4 V1 V3 100 30 10 60 10 20 50 5 V0 V2 V4 V3 V5 V0 始点终点D i 最短路径 V1V2V3V4V5 10 30100 10 30100 106030100 106030100 105030100 V0 V2 V0 V4 V0 V5 V0 V2 V0 V4 V0 V5 V0 V2 V0 V2 V3 V0 V4 V0 V5 V0 V2 V0 V2 V3 V0 V4 V0 V5 V0 V2 V0 V4 V3 V0 V4 V0 V5 10503090 V0 V2 V0 V4 V3 V0 V4 V0 V4 V5 10503090 V0 V2 V0 V4 V3 V0 V4 V0 V4 V5 10503060 V0 V2 V0 V4 V3 V0 V4 V0 V4 V3 V5 10503060 V0 V2 V0 V4 V3 V0 V4 V0 V4 V3 V5 如何在计算机中求得最短路径 Dijkstra提出了一个按路径 长度 递增的次序 逐步得到由给定源点到图的其余各点间的最短路径的算法 假设我们以邻接矩阵cost表示所研究的有向网 迪杰斯特拉算法需要一个顶点集合 初始时集合内只有一个源点V0 以后陆续将已求得最短路径的顶点加入到集合中 到全部顶点都进入集合了 过程就结束了 集合可用一维数组来表示 设此数组为S 凡在集合S以外的顶点 其相应的数组元素S i 为0 否则为1 另需一个一维数组D 每个顶点对应数组的一个单元 记录从源点到其他各顶点当前的最短路径长度 其初值为D i cost V0 i i 1 n 数组D中的数据随着算法的逐步进行要不断地修改定义了S集合和D数组并对其初始化后 迪杰斯特拉算法在进行中 都是从S之外的顶点集合中选出一个顶点w 使D w 的值最小 于是从源点到达w只通过S中的顶点 把w加入集合S中 并调整D中记录的从源点到集合中每个顶点v的距离 取D v 和D w cost w v 中值较小的作为新的D v 重复上述 直到S中包含V中其余各顶点的最短路径 V0V1V2V3V4V5V0 10 30100V1 5 V2 50 V3 10V4 20 60V5 V0 V2 V4 V3 V5 V1 V0 V2 V4 V3 V5 V0 V2 V4 V3 V0 V2 V4 V0 V2 S V0 V1 V5 V3 V4 V2 Vj V5 V4 V3 V2 V1 i 5 i 4 i 3 i 2 i 1 D终点 所有顶点对之间的最短路径 问题描述 已知一个各边权值均大于0的带权有向图 对每对顶点vi vj 要求求出每一对顶点之间的最短路径和最短路径长度 解决方案 1 每次以一个顶点为源点 重复执行迪杰斯特拉算法n次 这样 便可求得每一对顶点之间的最短路径 总的执行时间为O n3 2 形式更直接的弗洛伊德 Floyd 算法 时间复杂度也为O n3 弗洛伊德算法思想 假设求从顶点Vi到Vj的最短路径 如果从Vi到Vj有弧 则从Vi到Vj存在一条长度为arcs i j 的路径 该路径不一定是最短路径 尚需进行n次试探 首先考虑路径 Vi V0 Vj 是否存在 即判别 Vi V0 V0 Vj 是否存在 如存在 则比较 Vi Vj 和 Vi V0 Vj 的路径长度 取长度较短者为从Vi到Vj的中间顶点的序号不大于0的最短路径 假如在路径上再增加一个顶点V1 依次类推 可同时求得各对顶点间的最短路径 定义一个n阶方阵序列D 1 D 0 D 1 D 2 D k D n 1 其中 D 1 i j arcs i j D k i j Min D k 1 i j D k 1 i k D k 1 k j 0 k n 1可见 D 1 i j 就是从vi到vj的中间顶点的序号不大于1的最短路径的长度 D k i j 就是从vi到vj的中间顶点的序号不大于k的最短路径的长度 D n 1 i j 就是从vi到vj的最短路径的长度 各顶点间的最短路径及其路径长度 最短路径弗洛伊德举例 2 1 0 2