赋权图的最短路与关键路的算法与实现

《赋权图的最短路与关键路的算法与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西安石油大学本科毕业设计（论文）赋权图的最短路与关键路的算法与实现摘要：图形是由点和线构成的集合．赋权图的最短路就是任意两个节点之间的权值之和最小的路径．最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等．本文介绍了如何求最短路的有效算法:Dijkstra算法．它能求出赋权图的任何两个节点之间权值之和的最小路径.关键路径通常总是决定项目工期的进度活动序列．它是项目中从发点到收点的最长路径.关键路径法（CriticalPathMethod,CPM）是一种通过分析哪个活动序列（哪条路线）进

2、度安排的总时差最少来预测项目工期的一门网络分析技术．关键路径法,能推算出项目的最短完成时间和项目各项活动的可能开始和结束时间.关键词:图的邻接矩阵;最短路径;Dijkstra算法;关键路径西安石油大学本科毕业设计（论文）ThealgorithmandimplementationoftheShortestPathandtheCriticalPathＡbstract:Graphicsareconstitutedbythesetsofpointsandlines.Theshortestpathoftheweightedgraph

3、istheminimumsumoftheweightbetweenanytwovertices.Theshortestpathnotonlyreferstotheshortestdistance,butalsocanbeextendedtoothermetrics,suchastime,cost,linecapacityandsoon.Dijkstra’salgorithmwasthemostefficientalgorithmforhowtofindtheShortestPathofweightedgraph,which

4、isstudiedinthispaper.Dijkstra’salgorithmwasusedtocalculatetheminimumvalueofweightedgraphbetweenanytwovertices.Thecriticalpathisusuallyusedtoobtaintheprogressoftheprojectinactivities.Itisthelongestpathofaprojectfromthestartingpointtotheendingpoint.Thecriticalpathme

5、thod(CriticalPathMethod,CPM)whichanalysisasequenceoftheleasttimeinactivitiesorpredict(whichroute)theschedulebetter.Thecriticalpathmethodcanbeusedtocalculatetheshortestcompletiontime,startingandendingtimesinprojectactivities.Keywords:Adjacencymatrixofthegraph;TheSh

6、ortestPath;Dijkstra’salgorithm;TheCriticalPath西安石油大学本科毕业设计（论文）目录第一章绪论11.1课题的背景11.2课题的目的11.3课题的国内外研究状况11.4课题的意义和研究方法11.5课题的构成及主要研究内容2第二章基础知识22.1集合的概述22.2图论基础3第三章赋权图最短路的算法与应用93.1最短路的概念93.2最短路算法93.3Dijkstra算法103.4赋权图最短路算法在舰船通道路线设计中的应用13第四章关键路径法与应用154.1关键路径法的基本原理154.2

7、网络计划的特点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.2.1资源优化的种类275.2.2资源优化的原则285.3工期费用优化295.3.1工期与成本的关系295.

8、3.2工期与成本优化示例32总结37参考文献38致谢39附录A40附录B45西安石油大学本科毕业设计（论文）第一章绪论1.1课题的背景当前社会发展迅猛,人们为了顺应时代的发展,对于实际问题在认识并处理的过程中,探索到的解决问题的办法.像在求解网络图上节点间最短路径,工程进度计划的问题等.所以我们提出了这