1. 研究目的与意义、国内外研究现状（文献综述）
最短路径（NP）问题是网络优化问题的一个最基本也最重要的分支，面对社会经济时代的来临，信息将成为人类社会的财富之源。最短路径问题作为选择最优问题的基础，在众多研究和应用领域如电子导航、城市规划、计算机网络与通信、智能交通系统（ITS）、交通旅游、地理信息系统（GIS）以及工程技术等方面，都占有举足轻重的地位。许多的问题都可以形式化为一个特定的网络模型，然后反复求解最短路径这一子问题，目前，最短路径问题已成为众多学者广泛研究的一个热点问题。那什么是最短路径问题呢？用数学语言描述就是：对于一个指定的网络（由结点和路径组成的），找出一条路径，使得两结点间的距离最短。这里所谓的最短路径并不是我们生活中所理解的那种地理意义上的距离，而是能够延伸到其他层面的度量，像时间、容量以及费用都可以纳入路径的范畴。许多网络最优化问题最终可转化为最短路径问题，或者可用最短路的算法作为其子程序。而目前的研究工作主要集中于算法实现的优化改进与应用方面，最短路径问题通常有三类：第一，单源最短路径问题：包括确定源点的最短路径问题与确定汇点的最短路径问题；第二，确定源点和汇点的最短路径问题：即已知源点和汇点，求两顶点之间的最短路径；第三，全局最短路径问题：求图中所有顶点间的最短路径。同时，最短路径问题可以直接应用于生产生活的很多方面，如线路选择、网络铺设、石油运输等问题。最短路径问题的选择与实现也是计算机科学与地理信息科学等热门研究领域的基础,许多网络相关问题都可包含在最短路径问题的研究范围之中。因此，对于最短路问题的研究具有重要理论意义和实际意义，且有广阔的应用前景。
最短路径问题是图论研究中的经典算法问题。最短路径算法就是解决网络图中任意两个节点之间的最短路径，已经有了很长的研究历史，且算法理论也在不断地取得进步。并随着信息技术的发展，最短路问题在各学科领域中已成为对具有系统功能的模型进行分析与设计等不可缺少的理论，而且工程技术中很多有实用价值的问题与之相联系，实际中卓有成效的应用以及计算机应用软件的开发，又促进了其迅猛发展。
2. 研究的基本内容和问题
介绍最短路径问题以及有关图的一些基本概念、定义，然后，对求解最短路径的几种经典算法如 Dijkstra 算法、Bellman-Ford 算法、SPFA 算法和 Folyd 算法进行了简要的介绍和分析。
3. 研究的方法与方案
本文在深入分析已有算法的基础上，针对小规模网络最短路径这一问题，文中并对每种算法都给出了算法步骤，复杂度分析，可行性验证，以及具体实例分析，并以比较为目的说明了算法的优缺点，最后得出算法不仅思想简便、易于操作，同时有效的降低了算法时间复杂度，是计算小规模无回路网络的行之有效的算法，最后通过计算机语言对其进行了有力的验证，得到的结果完全一致。
4. 研究创新点
针对不同的网络图特征、具体的软硬件环境以及应用需求、算法复杂度等方面，采用不同的最短路径算法来实现。
5. 研究计划与进展
2013.12-2014.01 收集并整理资料，为毕业论文做准备。
2014.02-2014.03 理论研究，深入各个算法实现机制，做好技术准备。
2014.03-2014.04 编码测试。预期本阶段能够基本达到课题的研究目标。
