1、 西安石油大学本科毕业设计（论文） 赋 权 图 的 最 短 路 与 关 键 路 的 算 法 与 实 现摘 要：图形是由点和线构成的集合赋权图的最短路就是任意两个节点之间的权值之和最小的路径最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量, 如时间、费用、线路容量等本文介绍了如何求最短路的有效算法: Dijkstra 算法它能求出赋权图的任何两个节点之间权值之和的最小路径. 关键路径通常总是决定项目工期的进度活动序列它是项目中从发点到收点的最长路径.关键路径法（Critical Path Method,CPM）是一种通过分析哪个活动序列（哪条路线）进度安排的总时差最少来预测项目工期
2、的一门网络分析技术关键路径法,能推算出项目的最短完成时间和项目各项活动的可能开始和结束时间.关键词: 图的邻接矩阵; 最短路径; Dijkstra 算法; 关键路径西安石油大学本科毕业设计（论文） The algorithm and implementation of the Shortest Path and the Critical Path bstract: Graphics are constituted by the sets of points and lines. The shortest path of the weighted graph is the minimum sum
3、 of the weight between any two vertices. The shortest path not only refers to the shortest distance, but also can be extended to other metrics, such as time, cost, line capacity and so on. Dijkstras algorithm was the most efficient algorithm for how to find the Shortest Path of weighted graph, which
4、 is studied in this paper. Dijkstras algorithm was used to calculate the minimum value of weighted graph between any two vertices. The critical path is usually used to obtain the progress of the project in activities. It is the longest path of a project from the starting point to the ending point. T
5、he critical path method (Critical Path Method, CPM) which analysis a sequence of the least time in activities or predict (which route) the schedule better. The critical path method can be used to calculate the shortest completion time, starting and ending times in project activities.Keywords: Adjace
6、ncy matrix of the graph; The Shortest Path; Dijkstras algorithm; The Critical Path西安石油大学本科毕业设计（论文） 目 录第一章 绪论 .11.1 课题的背景 .11.2 课题的目的 .11.3 课题的国内外研究状况 .11.4 课题的意义和研究方法 .11.5 课题的构成及主要研究内容 .2第二章 基础知识 .22.1 集合的概述 .22.2 图论基础 .3第三章 赋权图最短路的算法与应用 .93.1 最短路的概念 .93.2 最短路算法 .93.3 Dijkstra 算法 .103.4 赋权图最短路算法在舰船
7、通道路线设计中的应用 .13第四章 关键路径法与应用 .154.1 关键路径法的基本原理 .154.2 网络计划的特点 .164.3 网络计划的分类 .174.4 网络计划关键路径的应用 .174.4.1 搭接网络计划示例 .174.4.2 搭接网络中的连接关系 .184.4.3 搭接网络计划的时间参数计算示例 .18第五章 网络计划优化 .245.1 工期优化 .24西安石油大学本科毕业设计（论文） 5.1.1 工期优化的计算步骤 .245.1.2 宜缩短持续时间的关键工作的选择 .245.1.3 按要求工期优化网络计划的方法 .245.1.4 工期优化示例 .265.2 资源优化 .275
8、.2.1 资源优化的种类 .275.2.2 资源优化的原则 .285.3 工期费用优化 .295.3.1 工期与成本的关系 .295.3.2 工期与成本优化示例 .32总 结 .37参考文献 .38致 谢 .39附录 A .40附录 B .45西安石油大学本科毕业设计（论文） 0第一章 绪论1.1 课题的背景当前社会发展迅猛, 人们为了顺应时代的发展, 对于实际问题在认识并处理的过程中, 探索到的解决问题的办法. 像在求解网络图上节点间最短路径, 工程进度计划的问题等. 所以我们提出了这一课题的研究. 特别是通过光纤网络经过十几年的高速建设与发展, 网络的规模越来越大, 业务也越来越丰富, 网
9、络建设已趋向成熟. 在这种背景下, 光纤网络资源的管理问题也就迫在眉睫了. 因此对应我们找到了解决问题的正确并且方便的答案. 而且现在的理论依据已经日趋完善, 也为了符合的当前的形势. 所以提出了这一课题.1.2 课题的目的为了解决当前社会活动过程中的现实问题. 运用先进的计算机手段, 实现从工程规划设计到资源管理的全面图形化、可视化管理,并提供多层面的网络性能分析与优化手段. 利用其从多个角度对最短路径算法进行联合优化. 生产出有便携式GPS 导航设备是集嵌入式技术、全球定位系统 GPS、地理信息系统 GIS、智能交通系统 ITS、计算机科学技术、多媒体技术和现代通信技术于一体的高科技产品.
10、1.3 课题的国内外研究状况现在国内外研究依然很热, 像基于 AOE 网络的关键路径方法研究 , 主要用于数字技术研究方向. 用关键路径法在挣值分析方法的研究, 资源约束的扩展关键路径法的研究. 在全球定位系统 GPS 导航方向的研究. 基于蚁群算法的最短路径搜索方法研究. 公交换乘最短路径算法研究, 基于 GIS 最短路径算法研究. 随机时间依赖网络的 K 期望寿命最短路径算法研究. 而在此我们主要研究的是图的最短路径和关键路径一系列问题. 建设项目管理是每个项目者所关心的重要内容之一. 就工程项目建设而言, 项目管理贯穿于项目建设的全过程. 关键路径法自 20 世纪 60年代传入中国后,
11、在生产中得到了应用,它符合工程施工的要求,特别适用于工程管理. 从国内外的情况看, 应用这种方法最多的是工程施工单位. 同国外发达国家相比, 目前我国在理论水平与应用方面相差无几, 但在应用管理上, 基本上停留在计划的编制上. 因此, 提高关键路径法在工程项目管理中的应用显得尤为重要.1.4 课题的意义和研究方法研究无线传感器网络中单、多跳通信方式的能耗规律, 结合 Dijkstra 最短路径递增的思想形成最小能耗路径拓扑的生成规则, 建立了一种基于最短路径树的拓扑结西安石油大学本科毕业设计（论文） 1构模型, 获得了每个节点到目的节点的最小能耗路径.从多个角度对最短路径算法进行联合优化.生产
12、出有便携式 GPS 导航设备是集嵌入式技术、全球定位系统 GPS、地理信息系统 GIS、智能交通系统 ITS、计算机科学技术、多媒体技术和现代通信技术于一体的高科技产品.以电信光纤网络管理为核心, 运用先进的计算机手段, 实现从工程规划设计到资源管理的全面图形化、可视化管理, 并提供多层面的网络性能分析与优化手段.在求解网络图上节点间最短路径的方法中, 目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)算法. 这种算法中 , 网络被抽象为一个图论中定义的有向或无向图 , 并利用图的节点邻接矩阵记录点间的关联信息. 在进行图的遍历以搜索最短路径时, 以该矩阵为基础不断进行目标值的最小性
13、判别, 直到获得最后的优化路径. Dijkstra算法是图论中确定最短路的基本方法, 也是其它算法的基础. 为了求出赋权图中任意两结点之间的最短路径, 通常采用这种方法, 是每次以一个结点为源点, 重复执行Dijkstra 算法 n 次.使用关键路径法（Critical Path Method,CPM）是一种通过分析哪个活动序列（哪条路线）进度安排的灵活性（总时差）最少来预测项目工期的网络分析技术. 具体而言, 该方法依赖于项目网络图和活动持续时间估计 , 通过正推法计算活动的最早时间,通过逆推法计算活动的最迟时间, 在此基础上确定关键路线, 并对关键路线进行调整和优化, 从而使项目工期最短,
14、 使项目进度计划最优.1.5 课题的构成及主要研究内容这篇论文可以进行如下的构成：第一章由绪论引入是开端, 包括毕业设计（论文）课题的背景及目的、国内外研究状况、课题的意义、研究方法、理论依据和具备的条件、毕业设计（论文）课题的构成及主要研究内容等.第二章简明扼要的概述了集合的相关理论以及图论的一些相关知识.第三章介绍图论中的最短路算法和应用.第四章介绍了关键路径法以及它的一些应用实例等内容.第五章着重介绍了网络计划的优化的三个方面：(1) 在现有条件的限制下,求工期最短;(2) 在规定的工期内 ,要求资源最均衡;(3) 加快工期而费用最少.西安石油大学本科毕业设计（论文） 2第二章 基础知识
15、2.1 集合的概述定义1 集合用于对象在一起的组. 一般情况下,是一组有相似的性质对象. 一个无序的一组对象我们定义为集合A, 其中的对象称为元素或集合的成员. 用a A来 表示元素a是集合A当中的元素. 用a A表示元素a不是集合A 当中的元素.集合一般是使用大写字母来表示. 小写字母通常用来表示元素的集合. 有多种方法来描述集合：列举法、维恩图、描述法等. 但是最常采用的是列举法和维恩图方法. 例如 : 元音字母在英文字母可以写成集合V = a, e, i, o, u . 通过维恩图来表示集合之间的关系的. 如下例:例2.1 画一维恩图用V表示, 在英文字母中集合用元音字母 .解 我们绘制
16、一个矩形来表示通用集U, 这是组26 个英文字母. 在这个矩形中我们画一个圆代表V. 在这个圈子, 我们指示V点为元音字母元素(见图1).图2-1 维恩图元音集合定义2 一个集合A是另一个集合 B的子集; 当且仅当A的每个元素也是B 的元素. 我们使用符号A B表示B集合的子集A. 当A B时,有对于 x(xAx B)是正确的. 若A不是B的子集, 我们只需要找到一个元素x A与x B , 举出这样的一个x反例来. 我们有这样一个有用的规则可以决定是否有一个集合是另一个集合的子集.在集合相关领域我们介绍很少, 是因为我们会用到一些相关的知识, 其次主要也是为后续的问题引线和做铺垫. 有了这些前
17、期的相关的储备知识, 我们就要进一步来研究图论当中的基本概念.西安石油大学本科毕业设计（论文） 32.2 图论基础定义1 设V 和E是两个有限非空集合, V中的元素叫做节点（或顶点） , E中的元素叫做边, 且E中的每一条边恰好与V中的两个节点相对应, 就称G = (V,E)是一个图.如下图2-2 ：图2-2定义2 若 G = (V, E)是一个图 , 若 E 中的每条边所对应的两个节点没有次序之分, 则称为无向图( 如图2-2 ）; 若 E 中的每条边所对应的两个节点有次序之分, 则称该图为有向图. 如下图2-3：图2-3注意：一般用小圆点或小圆圈表示节点, 用节点对连线表示边, 节点的位置
18、和连线的曲直及长短是无关的.在无向图中, 若边e与节点(a, b)对应, 则称e与节点 a关联, 同样, e与b关联. 若节点a和b之间有边连接, 则称节点a与b相邻, 否则不相邻. 若两条边关联一个共同的节点, 则称这两个边相邻, 否则, 若两条边不同时与任何一个节点关联, 则称这两个边不相邻. 有向图类似.定义3 关联同一个节点的边叫做自环. 在图2-3中, 像a, c, e 都有自环.定义4 不与任何节点相邻的节点称为孤立点. 如图2-3, 点f 就是孤立点.定义5 只与一条边关联的节点称为悬挂点. 如图2-4中的d点.西安石油大学本科毕业设计（论文） 4图2-4 定义6 如果顶点个数V
19、与边的条数E都是有限的, 图G就是有限图. 如果V =1, E=0,图G称为平凡图. 这种仅含一个孤立点的图是有限图的特例. 如果V或E 是无限的, 图G称为无限图.定义7 如果一个图没有自环, 并且每两个顶点之间最多只有一条边, 这样的图称为简单图. 如图2-5：图2-5定义8 设图G = (V, E), V, 其中的所有边都在E当中. i=1,2,3, p, 所有边与iv节点 与 关联 . 而且顶点和边交替出现, 将这样的一个交替序列称为路. ivj图2-6如图2-6 中a-b-d-c就是一条路.定义10 若从起始节点出发结束到起始结点, 称这条路为回路或圈.如图2-6中a-b-d-c-a
20、就是一条回路.定义11 如果图G中任意节点u到任意节点v都是有路相连的, 则称G 为连通图, 否则是非连通图. 如图2-7：西安石油大学本科毕业设计（论文） 5图2-7定义12 一个没有重边的图用一种方法将图的边可以一一列出来; 另一种方式是使用邻接矩阵. 假设G = (V, E)是一个简单的图, |V| = n. 假设v 1,v2 ,vn 作为G的任意顶点, G的邻接矩阵就是这个图的边的顶点, 所构成的矩阵（nn）的（0 - 1）矩阵. 当 vi和v j是相邻的时候 , 矩阵对应位置的值为1, 当它们不相邻时候, 对应值为0. 换句话说, 如果其邻接矩阵是一个A nn= , 那么ija其 它 相 邻如 果 0,jiija例2.2 用邻接矩阵来表示如图2-8.图 2-8 解 顶点为a, b, c , d. 这个图的邻接矩阵是：定义 13 若图 G=(V, E)中各边 e 都赋有一个实数 W(e), W(e)是一个实数集, W中的每个数与 E 中的一个边相对应, W(e)对应的实数称为边 e 的权, 这个图则称这种图为赋权图, 记为 G = G(V, E, W). 如图 2-9:
