本科生毕业设计（论文）题目：线性表的设计和实现学生姓名：张三学号： 1153院系：基础科学学院信息技术系专业年级：2012级信息与计算科学专业指导教师：李四年月日摘要随着现代物流业的发展，如何优化和配置物流的运输路径成为了一个热点的问题。

其中，最具代表性的问题就是如何在一个道路网络中选择两点之间的合适路径，使其距离最短。

为了解决这个问题，本文介绍了两种最常用的最短路径求解方法——DIJKSTRA算法与FLOYD算法，分析了它们的适用范围以及时间复杂度。

最后，对一个具体的航空公司物流配送问题进行了求解，得到了理论最优路径。

关键词：最短路径问题；DIJKSTRA算法；物流运输ABSTRACTWith the development of modern logistics industry, how to optimize and configure the transport path of logistics has become a hot issue. Among them, the most representative problem is how to select the appropriate path between two points in a road network to minimize the distance. In order to solve this problem, this paper introduces two most common shortest path solutions ——Dijkstra algorithm and Floyd algorithm, and analyzes their application range and time complexity. Finally, a specific airline logistics distribution problem is solved, and the theoretical optimal path is obtained.Keywords：Minimum path problem；Dijkstra algorithm；Logistics transportation目录第一章引言研究背景在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。

顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示。

最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。

因此掌握最短路问题具有很重要的意义。

研究现状本节主要讨论两个方面的问题，首先简要回顾最短路径算法研究现状，然后概要总结最短路径算法分类。

最短路径算法研究现状最短路径问题一直是计算机科学、运筹学、地理信息科学等学科领域的研究热点。

国内外大量专家学者对此问题进行了深入研究。

经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。

常用的路径规划方法有:平行最短路径搜索算法，蚁群算法，基于矩阵负载平衡的启发算法, EBSP*算法和Dijkstra算法等。

创门在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色但是因为Dijkstra算法可以给出最可靠的最短路径，并且容易实现，所以备受青睐和并被广泛应用。

经典的Dijkstra算法的时间复杂度为，直接应用到大规模城市路网时，最短路径查询时间难以令人接受，专家学者纷纷开展Dij kstra优化算法研究，概括起来，以往研究者主要是从5个方面对最短路径算法进行性能优化：(1)基于数据存储结构的优化，以空间换取时间；( 2 )基于路网规模控制的优化；(3)基于搜索策略的优化；( 4 )优先级队列结构的优化；( 5 )基于双向搜索的并行计算优化。

最短路径算法分类由于问题类型、网络特性的不同，最短路径算法也表现出多样性。

(1)按照最短路径问题分类，最短路径问题通常可分为2个基本类型：一是单源最短路径问题，即查找某一源点到其余各点的最短路径；另一类是查找某个节点对之间的最短路径。

最短路径问题具体可细分为以下几种，单源最短路径问题，单对节点间最短路径、所有节点间最短路径、k则最短路径、实时最短路径、指定必经节点的最短路径以及前N条最短路径问题等，本文的研究范畴属于单对节点间最短路径问题。

(2)按照网络类型和表示方法分类，网络可以分为稀疏网络和非稀疏网络，常用的表示方法有邻接矩阵和邻接表。

邻接矩阵方法能够在时间内查询到任意两个节点之间是否有一条边，它的空间复杂度为。

现实生活中网络节点往往很多，动辄上万，而且是稀疏网络居多，比如城市路网，所以用邻接矩阵表示既不现实，又浪费空间。

邻接表是另一种存储网络拓扑的数据结构，它是一种链式存储结构，对于交通网络等稀疏图，采用邻接表数据结构存储网络拓扑数据空间复杂度仅为，不存在存储空间的浪费。

邻接表数据结构已被证明是网络表达中最有效率的数据结构，在最短路径算法中得到了广泛应用。

第二章 最短路径问题的基本理论知识最短路问题的定义最短路问题（short-path problem ）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点，（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，可用来解决管道铺设，线路安装，厂区布局和设备更新等实际问题。

最短路问题的Dijkstra 算法Dijkstra 算法的局限性在了解和使用某种算法之前，我们先要明白这种算法有怎样的局限性。

只有深入理解来每一种算法的局限性，才能根据具体的问题选择合适的算法来求解。

Dijkstra 算法最大的局限性在于不能够处理带有负边的图，即图中任意两点之间的权值必须非负。

如果某张图中存在长度为负数的边，那么Dijkstra 算法将不再适用，需要寻找其他算法求解。

Dijkstra 算法求解步骤(1) 先给图中的点进行编号，确定起点的编号。

(2) 得到图的构成，写出图的矩阵(3) 根据要求求出发点S 到终点E 的最短距离，那么需要从当前没被访问过的结点集合unvist={u | u {1,2,3...}}n ∈中找到一个距离已经标记的点的集合中vist={u | u {1,2,3...}}n ∈的最短距离，得到这个顶点；(4) 利用这个顶点来松弛其它和它相连的顶点距离S 的值(5) 重复步骤(2)和(3)，直到再也没有点可以用来松弛其它点，这样我们就得到了由起点S 到其它任意点的最短距离。

Dijkstra 算法的时间复杂度 我们可以用大符号将Dijkstra 算法的时间复杂度表示成边数m 与顶点数n的函数。

?Dijkstra 算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q ，因此搜索Q 中最小元素的运算(Extract-Min(Q))只需要线性搜索Q 中的所有元素，据此我们可以知道算法的时间复杂度是。

?对于边数少于n 2稀疏图而言，我们可以用邻接表来更有效的实现Dijkstra算法。

为了达到这一目的，需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。

当用到二叉堆的时候，算法所需的时间为简单案例分析给出对应的结点之间的关系（表2-1为对应的结点之间的关系）长度 A B C D E A 0 2 15 10 10 B 2 0 11 1 5 C 15 11 1 20 7 D 10 10 20 0 3 E1057 3表2-1需要注意的是，其中（A,B ）= 2 表示结点A 到B 的长度为2 第一步：进行编号，假定A 点即为起点。

第二步：得到图第三步：首先从起点A 开始找到距离A 最近的点，那就是A 点了； 第四步：把A 点标记到已经用过的的集合用A 来更新其它点到起点的距离得到的集合表示起点到B,C,D,E 的距离分别为2,15,10,10第五步：重复上述步骤：得到{,}vist A B =,{,,}unvist C D E =,dist =021337A B C D E继续重复上述步骤，最后的到{,,,,}vist A B C D E =,unvist =∅,得到的dist =021336A B C D E，即最短路求解完毕。

最短路问题的Floyd 算法算法定义除了Dijkstra 算法，另外一种简单的最短路算法是floyd 算法，它也经常被用于解决含有有向图或者是负权的最短路径问题，并且能够用于计算有向图的传递闭包。

该算法的时间复杂度为，空间复杂度为。

算法思想原理Floyd 算法是非常常见的使用动态规划来寻找最优路径的算法。

如果我们用简单的语言解释，总体要实现的目标是找到从点i 到点j 的最短路径。

如果我们换一个角度，从动态规划的角度观察，那就必须得要对这个目标进行一个重新的诠释。

从任意节点i 到任意节点j 的最短路径不外乎2种可能，1是直接从i 到j ，2是从i 经过若干个节点k 到j 。

所以，我们假设Dis(i,j)为节点u 到节点v 的最短路径的距离，对于每一个节点k ，我们检查是否成立，如果成立，证明从i 到k 再到j 的路径比i 直接到j 的路径短，我们便设置，这样一来，当我们遍历完所有节点k ，Dis(i,j)中记录的便是i 到j 的最短路径的距离。

算法过程描述（1）从任意一条单边路径开始。

所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

（2）对于每一对顶点u 和v ，看看是否存在一个顶点w 使得从u 到w 再到v 比己知的路径更短，如果是的话需要更新它。

算法适用范围⑴ 无向图最短路问题；?⑵ 稠密图效果最佳；? ⑶ 边权可正可负。

算法简单实例图3-2 无向图根据图3-2，用Floyd算法找出任意两点的最短路径步骤如下表3-2：distk[1] distk[2] distk[3] MIN A->B 1 3 7 1 A->C 1 3 5 * 1 A->D 3 3 5 3 B->C 2 2 6 2 B->D * 4 4 * 4 C->D 2 4 6 2表3-2 Floyd算法步骤流程第三章实际案例分析问题描述问题的背景及假设网上购物一直是常见的消费方式，其依托于物流业逐渐蓬勃发展，每个送货人员都需要以最快的速度送货，而且往往会发送多个地方，所以有必要设计耗时最小的路线。