文档介绍：该【最短路径算法在物流运输中的应用 】是由【Duan940628】上传分享，文档一共【54】页，该文档可以免费在线阅读，需要了解更多关于【最短路径算法在物流运输中的应用 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。CKBOODwasrevisedintheearlymorningofDecember17,2020.
最短路径算法在物流运输中的应用
本科生毕业设计(论文)
题目:线性表的设计和实现
学生姓名:张三
学号:1153
院系:基础科学学院信息技术系
专业年级:2012级信息与计算科学专业
指导教师:李四
注:;中英文摘要正反打印一张纸;目录、正文、参考文献、致谢、附录均独立正反打印!
,教学院(系)可自行商定。
年月日
摘要
随着现代物流业的发展,如何优化和配置物流的运输路径成为了一个热点的问题。其中,最具代表性的问题就是如何在一个道路网络中选择两点之间的合适路径,使其距离最短。为了解决这个问题,本文介绍了两种最常用的最短路径求解方法——DIJKSTRA算法与FLOYD算法,分析了它们的适用范围以及时间复杂度。最后,对一个具体的航空公司物流配送问题进行了求解,得到了理论最优路径。
关键词:最短路径问题;DIJKSTRA算法;物流运输
ABSTRACT
Withthedevelopmentofmodernlogisticsindustry,,,thispaperintroducestwomostcommonshortestpathsolutions——DijkstraalgorithmandFloydalgorithm,,aspecificairlinelogisticsdistributionproblemissolved,andthetheoreticaloptimalpathisobtained.
Keywords:Minimumpathproblem;Dijkstraalgorithm;Logisticstransportation
目录
第一章引言 1
研究背景 1
研究现状 1
最短路径算法研究现状 1
最短路径算法分类 2
第二章最短路径问题的基本理论知识 3
最短路问题的定义 3
最短路问题的Dijkstra算法 3
Dijkstra算法的局限性 3
Dijkstra算法求解步骤 3
Dijkstra算法的时间复杂度 4
简单案例分析 4
最短路问题的Floyd算法 5
算法定义 5
算法思想原理 5
算法过程描述 6
算法适用范围 6
算法简单实例 6
第三章实际案例分析 7
问题描述 7
问题的背景及假设 7
符号说明 7
模型的建立与求解 8
模型一 8
模型二 10
第四章总结 15
优点 15
缺点 15
参考文献 16
致谢 17
附录 18
附录A实际案例背景数据 18
第一章引言
研究背景
在现实生活中中,我们经常会遇到图类问题,图是一种有顶点和边组成,顶点代表对象,在示意图中我们经常使用点或者原来表示,边表示的是两个对象之间的连接关系,在示意图中,我们使用连接两点G点直接按的下端来表示。顶点的集合是V,边的集合是E的图记为G[V,E],连接两点u和v的边用e(u,v)表示。最短问题是图论中的基础问题,也是解决图类问题的有效办法之一,在数学建模中会经常遇到,通常会把一个实际问题抽象成一个图,然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。
研究现状
本节主要讨论两个方面的问题,首先简要回顾最短路径算法研究现状,然后概要总结最短路径算法分类。
最短路径算法研究现状
最短路径问题一直是计算机科学、运筹学、地理信息科学等学科领域的研究热点。国内外大量专家学者对此问题进行了深入研究。
经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。常用的路径规划方法有:平行最短路径搜索算法,蚁群算法,基于矩阵负载平衡的启发算法,EBSP*算法和Dijkstra算法等。创门在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色但是因为Dijkstra算法可以给出最可靠的最短路径,并且容易实现,所以备受青睐和并被广泛应用。
经典的Dijkstra算法的时间复杂度为,直接应用到大规模城市路网时,最短路径查询时间难以令人接受,专家学者纷纷开展Dijkstra优化算法研究,概括起来,以往研究者主要是从5个方面对最短路径算法进行性能优化:(1)基于数据存储结构的优化,以空间换取时间;(2)基于路网规模控制的优化;(3)基于搜索策略的优化;(4)优先级队列结构的优化;(5)基于双向搜索的并行计算优化。
最短路径算法分类
由于问题类型、网络特性的不同,最短路径算法也表现出多样性。
按照最短路径问题分类,最短路径问题通常可分为2个基本类型:一是单源最短路径问题,即查找某一源点到其余各点的最短路径;另一类是查找某个节点对之间的最短路径。
最短路径问题具体可细分为以下几种,单源最短路径问题,单对节点间最短路径、所有节点间最短路径、k则最短路径、实时最短路径、指定必经节点的最短路径以及前N条最短路径问题等,本文的研究范畴属于单对节点间最短路径问题。
按照网络类型和表示方法分类,网络可以分为稀疏网络和非稀疏网络,常用的表示方法有邻接矩阵和邻接表。
邻接矩阵方法能够在时间内查询到任意两个节点之间是否有一条边,它的空间复杂度为。现实生活中网络节点往往很多,动辄上万,而且是稀疏网络居多,比如城市路网,所以用邻接矩阵表示既不现实,又浪费空间。
邻接表是另一种存储网络拓扑的数据结构,它是一种链式存储结构,对于交通网络等稀疏图,采用邻接表数据结构存储网络拓扑数据空间复杂度仅为,不存在存储空间的浪费。邻接表数据结构已被证明是网络表达中最有效率的数据结构,在最短路径算法中得到了广泛应用。