赋权图的最短路与关键路的算法与实现摘要：图形是由点和线构成的集合．赋权图的最短路就是任意两个节点之间的权值之和最小的路径．最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等．本文介绍了如何求最短路的有效算法:Dijkstra算法．它能求出赋权图的任何两个节点之间权值之和的最小路径.关键路径通常总是决定项目工期的进度活动序列．它是项目中从发点到收点的最长路径.关键路径法（CriticalPathMethod,CPM）是一种通过分析哪个活动序列（哪条路线）进度安排的总时差最少来预测项目工期的一门网络分析技术．关键路径法,能推算出项目的最短完成时间和项目各项活动的可能开始和结束时间.关键词:图的邻接矩阵;最短路径;Dijkstra算法;关键路径ThealgorithmandimplementationoftheShortestPathandtheCriticalPathＡbstract:Graphicsareconstitutedbythesetsofpointsandlines.Theshortestpathoftheweightedgraphistheminimumsumoftheweightbetweenanytwovertices.Theshortestpathnotonlyreferstotheshortestdistance,butalsocanbeextendedtoothermetrics,suchastime,cost,linecapacityandsoon.Dijkstra’salgorithmwasthemostefficientalgorithmforhowtofindtheShortestPathofweightedgraph,whichisstudiedinthispaper.Dijkstra’salgorithmwasusedtocalculatetheminimumvalueofweightedgraphbetweenanytwovertices.Thecriticalpathisusuallyusedtoobtaintheprogressoftheprojectinactivities.Itisthelongestpathofaprojectfromthestartingpointtotheendingpoint.Thecriticalpathmethod(CriticalPathMethod,CPM)whichanalysisasequenceoftheleasttimeinactivitiesorpredict(whichroute)theschedulebetter.Thecriticalpathmethodcanbeusedtocalculatetheshortestcompletiontime,startingandendingtimesinprojectactivities.Keywords:Adjacencymatrixofthegraph;TheShortestPath;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关键路径法的基本原理.........................
