文献综述
一、研究目的及意义
最短路径问题的研究起源于20世纪50年代末的一些数学游戏，是图论中的一个经典问题。它的基本内容是：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。 最短路问题不仅在数学理论及其应用中是一种非常有用的工具，而且实际生活中可用来解决管路铺设、线路安装、厂区布局和设备更新等问题。因此，对最短路模型及其应用的研究具有重大意义。
二、研究现状
最短路径算法一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。它的应用十分广泛，国内外许多学者对其进行了广泛研究,获得了许多研究成果。
1959年，荷兰计算机科学家Edsger Wyde Dijkstra提出赋权图的有效算法，也就是众所周知的Dijkstra算法。Dijkstra算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。该算法能够解决两指定点间的最短路，也可以求解图中一特定点到其它各顶点的最短路，其时间复杂性为。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。
后来Richard Bellman和Ford提出Bellman–Ford,主要解决允许弧权重为负的单源最短路问题。它的原理是对图进行次松弛操作，得到所有可能的最短路径。其优点是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达。但算法可以进行若干种优化，提高了效率。
1962年，Robert W．Floyd提出Floyd算法，又称为插点法，这是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，主要解决允许弧权重为负任意两对顶点之间的最短路问题。其时间复杂性为。
1994年，段凡丁将SPFA 算法引进中国。SPFA 算法是Bellman-Ford的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同。
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
