考研

　　2019考研备考已经开始了，为帮助大家快速进入备考状态，文都网校考研频道小编特意帮大家整理了计算机考研的知识点：图的应用之最短路径，希望对计算机考研的考生们有所帮助!

　　图是数据结构科目中难度最大的重点章节，在这两年的考试中也作为重点来考查。图这部分内容概念多、算法多、难度大。这就需要大家深刻理解每个知识点，多做练习，抓住规律，才能很好地解答这部分试题。图这部分要求大家掌握图的定义、特点、存储结构、遍历、图的基本应用等内容。图这部分的重点和难点是图的基本应用，这在09年和10年的考试中有所体现。图的基本应用包括：最小生成树、最短路径、拓扑排序、关键路径等。09年考试中重点考查了最短路径的判断与证明。建议大家把图的基本应用作为重点来复习。

　　下面介绍一下图的基本应用：

　　二、最短路径

　　最短路径问题是与日常生活密切相关的问题，例如：路线选择、计算机网络路由选择等，同时也是考试重点之一。下面分两种情况讨论了最短路径问题。

　　最短路径算法：

　　1.Dijkstra算法

　　Dijkstra算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

　　定义G=(V,E)，定义集合S存放已经找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点，即有T=V-S ：

　　Dijkstra算法描述如下：

　　(1)假设用带权的邻接矩阵edges来表示带权有向图，edges[i][j]表示弧上的权值。若不存在则置edges[i][j]=∞(计算机上用一个允许的最大值代替)。S为已经找到的从Vs出发的最短路径的终点集合，它初始化为空集。那么，从Vs出发到图上其余各顶点(终点)Vi可能达到的最短路径长度的初值为：D[i]=deges[s][i] Vi∈V

　　(2)选择Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是当前求得的一条从Vs出发的最短路径的终点。令S=S∪{Vj}

　　(3)修改从Vs出发到集合V-S上任一顶点Vk可达的最短路径长度。如果D[j]+edges[j][k]

　　重复操作(2)(3)共n-1次。由此求得从Vs到图上其余各顶点的最短路径。

　　2.Floyd算法

　　Floyd算法的核心思想是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

　　建议大家重点掌握这两种最短路径算法，并多做习题来巩固。

　　文都网校考研频道为大家持续更新考研资料，希望能帮助到大家，同学们可以关注文都考研，这里有你需要的资料，点击【kaoyan.wenduedu.com】风里、雨里，文都陪伴着你！有问题找文都☞☞☞详情咨询入口>>>

资讯推荐：

　　全国各大高校2018考研成绩查询时间及入口

　　历年考研复试分数线(34所自划线院校)

　　2018考研复试备考指导汇总

　　全国各院校2018考研调剂信息汇总

课程推荐：