[2018年最新整理]#第四部分非线性部分之图(第10章).ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 说明：一个无向图的生成树不唯一。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 湖北工业大学计算机学院 沈华 * 顶点事件的最晚发生时间 (与逆拓扑排序有关) 其中，i，j是顶点编号。 AOE网的关键路径 湖北工业大学计算机学院 沈华 * 【举例说明】 V1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 V2 V3 V4 V5 V6 V7 V8 V9 18 6 0 4 5 7 7 14 16 18 16 14 7 10 8 6 6 0 湖北工业大学计算机学院 沈华 * 活动的最早发生时间 活动的最晚发生时间 其中，i，j是顶点编号。 AOE网的关键路径 湖北工业大学计算机学院 沈华 * [举例说明] V1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 V2 V3 V4 V5 V6 V7 V8 V9 18 6 0 4 5 7 7 14 16 18 16 14 7 10 8 6 6 0 0 0 0 6 4 5 7 7 7 边活动 最早发生时间 最晚发生时间 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 16 14 0 2 3 6 6 8 7 7 10 16 14 湖北工业大学计算机学院 沈华 * 关键路径 由表示关键活动的有向边构成的从源点到汇点的有向路径。 即为从源点到汇点的最长路径。 其意义在于：计算完成工程至少需要的时间，并找出影响工程进度的关键活动。 AOE网的关键路径 湖北工业大学计算机学院 沈华 * 关键路径的长度 关键路径上有向边的权值之和。 逻辑上表示至少花多少时间才能完成工程。 AOE网的关键路径 湖北工业大学计算机学院 沈华 * [举例说明] V1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 V2 V3 V4 V5 V6 V7 V8 V9 18 6 0 4 5 7 7 14 16 18 16 14 7 10 8 6 6 0 0 0 0 6 4 5 7 7 7 边活动 最早发生时间 最晚发生时间 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 16 14 0 2 3 6 6 8 7 7 10 16 14 * * * * * * * * * * * * * * * * * * * * * * * * * 湖北工业大学计算机学院 沈华 * 所谓单源最短路径问题是指，给定一个有向网络N，要求找出从某个顶点v到N中其余各顶点的最短路径。Dijkstra提出了一种基于贪婪的求解算法，通常称为求解单源最短路径的Dijkstra（迪杰斯特拉）算法。 单源最短路径 湖北工业大学计算机学院 沈华 * 迪杰斯特拉(Dijkstra)算法的原理 按路径长度递增次序产生源点到各顶点的最短路径。 单源最短路径 湖北工业大学计算机学院 沈华 * 【Dijkstra算法中所涉及到的数据结构】 图的邻接矩阵 (或者邻接表) 一维数组S[1..n]：记录从源点到相应顶点的最短路径是否已确定。 一维数组D[1..n]：记录源点到相应顶点的路径长度。算法结束时，D记录了源点到各个顶点的最短路径的长度。 一维数组P[1..n]：记录路径上相应顶点的直接前驱顶点的编号。 湖北工业大学计算机学院 沈华 * 【Dijkstra算法描述】 1 初始化辅助数据结构：(i=1..n) ① S[i] = 0； ② D[i] = G.vexs[v][i]； ③ 若D[i]不为?，则P[i] = v，否则P[i] = -1。 2确定源点自身的最短路径: S[v] = 1, D[v] = 0。 3循环确定v到其余n-1个顶点的最短路径： ①在D中找出未确定最短路径的顶点中路径最小的顶点，设该顶点序号为k； ②若D[k] 为?，则退出本算法，否则执行③ ； ③ 赋值S[k]=1； ④对还未确定最短路径的顶点j进行如下调整： D[j] D[k] + G[k][j]，则D[j] = D[k] + G[k][j]，P[j]=k。 设v为源点 湖北工业大学计算机学院 沈华 * 【Dijkstra算法描述】 4 依次打印各顶点的最短路径及其长度： (i=1..n) ① write(i，D[i])；