最短路问题的算法及其应用开题报告

全文总字数：1447字

1. 研究目的与意义

图论是应用数学的一个分支，它的概念和结果来源非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题，博弈问题，棋盘上马的行走路线问题等，这些古老的难题，当时吸引了很多学者注意。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离，还可以引申到它的度量，如时间，费用，线路容量等。最短路径算法的选择与实现是通道路线设计的基础，最短路径算法是计算机科学与地理信息科学等领域的研究热点，很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。

课题研究图论中关于最短路问题的算法和应用。最短路问题具有实际的应用价值，同时兼具理论的研究意义。研究目的是对经典的算法加以归纳描述，并给出算法的编程实现。对已有的算法，考虑是否可以提高计算效率，加以改进。

2. 国内外研究现状分析

余丽介绍了最短路的两种算法，并介绍了它们在物流管理中的若干应用. 将dijkstra 算法与 floyd 算法用于解决物流管理中的配送路径问题以及配送中心选址问题，并对这两种算法进行比较.

曹旭，张喆，马少仙利用floyd 算法探究了最短路问题，经过matlab实现后将其应用到旅游线路优化设计中。选取了甘肃及周边地区13个旅游景点，求得从任意景点出发到任意目的景点的最短路，以及途中必须给定两个景点的最短路问题。

矩阵算法是求解不含负回路的网络中所有顶点对之间最短路的有效算法之一,但当节点比较多时,计算的矩阵多,重复计算量大,降低了计算效率。为此,林华珍,周根贵提出了一种优化的矩阵算法,该算法的思路是利用权矩阵计算网络任意两节点之间的最短路长。计算实例表明,优化的矩阵算法减少了重复计算,简化了路径标注方法,提高了计算效率。

3. 研究的基本内容与计划

研究内容：

（1） 编写dijkstra算法与floyd算法的程序，结合具体实例，演示计算过程；

（2） 尝试改进与优化算法。

4. 研究创新点

（1）原理、方法和论证分析相结合。