毕业论文移动版

在二十世纪初,最短路问题就已经被高度重视了，那时候有很多科学家都致力于对这个问题的探索研究。直到一位来自荷兰的科学家Edsger Wybe Dijkdtra才在1959年给出最短路问题求解的基本思路，而且也给出了算法。很久以来，最短路算法在交通科学研究中有很大的作用，最短路算法相关的问题更是多种多样。近年来随着智能交通系统与地理的信息系统的相结合，最短路算法在交通运输网路的问题中的地位也越来越高。它同时也是资源的分配，路线的设计以及分析优化等问题的基础。国内外大量专家也对此不断的进行了深入探索。对于最短路的研究，国内外研究的内容集中在网路的算法研究，并且主要的研究对象都是算法本身，比如Floyd算法，Dijkstra算法，SPFA算法之类，适用于寻找网路最短路的算法的最优解。目前国内外研究的对象主要还是算法本身，应用层面的很少，但是通过对算法的优劣比较才能得到真正的最优解。而且目前对于算法的探索过度关注于算法在交通运输问题上的适应性却忽略了其应用的通用性。当时Dijkstra提出了一个了算法，这个算法是为了求解从固定的起点到其它的点之间的最短路问题，也就是现在成了众所周知的Dijkstra算法，是最为经典的算法之一。87194

目前最为常用的最短路算法有以下三种：第一种是基于图论的理论的算法；第二种是基于人工智能理论的算法；第三种是基于智能控制的算法。特别是近十几年，智能控制技术广泛的应用于交通运输网路问题，学者们的兴趣也由对前两种算法的改进研究转向了对第三种算法的研究去了。论文网

对于最短路算法的研究包含了两个主要的方面。一方面为最短路径问题（完全信息情况下），Bellman（1958）、Dijkstra（1959）和Dreyfus（1969）已发展出许多高效算法。这些算法已成为确定情况下的经典算法。（当在不确定的情况下时）最短路问题的研究通常包含以下几个方面：Frank(1969)以及Mirchandani（1976）主要研究了路径的长度随机变化而且在非时间独立情况之下的最短路问题；L oui（1983）、Muethy和Sarkar（1996）研究了考虑不同的费用函数的最短路问题；汪泽焱和刁兴春在2004年研究了非线性约束最短路问题的启发式算法；王欣在2007年研究了含负权有向图最短路问题的一种新算法；朱建明和沙丹2008年对时变网络中零等待时间的最短路径问题提出了一个对偶算法；李博、李宁、康慧燕和元春梅等在2011年根据大型稀疏网络的特点，给出了新的最短路算法。

国内外公认的经典的算法有Dijkstra及Floyd算法。这两种算法中，这两种网路抽象化为图论中的有向以及无向图，利用图的点来连接矩阵记录点间的相关的信息。在进行图的讨论以搜索最短路径时，是先以该矩阵为基础，然后一步步地进行目标值的最小性判别，最后获得最优路径。