学海网

毕业论文 网络最短路径问题，共52页，21443字
第一章 绪论
二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题是图论中的一个典范问题，它已经被应用于众多领域.最短路径问题最直接的应用当数在地理信息领域，如：GIS网络分析、城市规划、电子导航等.在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子.在网络通信领域，信息包传递的路径选择问题也与最短路径问题息息相关.举个例子，OPSF开放路由选择协议，每个OPSF路由器都维护一个描述自治系统拓扑结构的数据库，通过这个数据库构建最短路径树来计算路由表，从而跟踪自治系统范围内到每个目标的最短路径.在图象分割问题中，最短路径也有直接的应用：在语音识别中，一个主要的问题就是区别同音词，例如，to、two、too.为解决这个问题，我们需要建一个图，顶点代表可能的单词，边连接相邻的单词，边上的权代表相邻的可能行大小.这样图中的最短路径，就是对句子的最好解释.
由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产生了一些经典的算法.近些年来，对最短路径研究的热度依然不减，并且时间复杂度降得越来越低.所以在本课题中我们将提出不仅是以前我们学习过的一些经典的算法，我们还将提出一些以前没有学习过的更有应用空间的算法.以及各算法之间的比较.最后还将把这些算法在现实中的应用最一些简单的介绍.
.....