基于DIJKSTRA算法的最短路径搜索仿真毕业设计使用说明书.docx
《基于DIJKSTRA算法的最短路径搜索仿真毕业设计使用说明书.docx》由会员分享，可在线阅读，更多相关《基于DIJKSTRA算法的最短路径搜索仿真毕业设计使用说明书.docx（38页珍藏版）》请在冰点文库上搜索。
基于DIJKSTRA算法的最短路径搜索仿真毕业设计使用说明书
毕业设计说明书
基于Dijkstra算法的最短路径搜索仿真
摘要
GIS地理网络分析功能中的一个最重要问题就是最短路径分析。
最短路径问题中最经典的算法便是Dijkstra算法，该理论是很大一部分工程项目解决最短路径问题的基础。
传统的Dijkstra算法在求解节点之间的最短路径时，对已经标识的节点以外的很多节点进行了计算，因此算法的速度受到了影响。
在传统Dijkstra算法分析的基础上，进行改进和优化，最短路径上节点的邻接点被进行了处理，从而得到了算法优化，但其余的节点不受到波及。
因此，在优化算法中计算的节点数量大幅减少，使算法的运算在速度上得到了大量的提升。
关键词：
最短路径，Dijkstra算法，仿真
Abstract
Shortestpathanalysisisthekeyproblemofnetworkanalyses，Dijkstraalgorithmisaclassicarithmeticfortheshortestpath.Itistheacademicfoundationthatmanyengineeringsweresolvedintheshortestpathissue.WhenashortestpathbetweennodesissearchedwithDijkstraalgorithm，alotofnodesawayfromlaggednodesareinvolved，sothattheefficiencyofDijkstraalgorithmislow．AnoptimizationalgorithmispresentedinthispaperbasedonanalysisofDijkstraalgorithm．Onlythesenodesthattheneighborofnodesintheshortestpathareprocessed，andothernodesarenotprocessed.Therefore，thenumberofprocessednodesislargelyreducedintheoptimizationalgorithm，andefficiencyoftheoptimizationalgorithmisimproved．
Keywords:
theshortestpath，Dijkstraalgorithm，Simulation
第一章引言
1.1课题的目的意义
最短路径问题是图论、网络分析研究的重要课题，它被广泛用于网络优化，交通运输，物流配送，电子导航等领域。
最短路径问题不单单是“纯距离”的最短路径，也可以被扩展来衡量其他的意义，如经济成本，时间和吞吐量。
例如，城市交通，旅客选择旅游的最佳路径，最可靠的路径运输网络，的最大容量，最少的成本问题，和统筹方法关的键路径问题，全部可以转化为最短路径问题。
最短路径问题要解决的就是加权图G=两给定定点之间的最短路径。
求单源点最短路径的一个著名算法是Dijkstra算法。
最短路径要解决的问题是一个加权图G=到两个给出的定点之间的最短路径。
寻求一个单源最短路径算法就是众所周知的Dijkstra算法。
Dijkstra（迪杰斯特拉）算法是典型的单源最短路径算法，用于计算任意节点到其它所有节点的最短路径。
以最初始的点为中心，向外层拓展，直到拓展到终点为止，是其最重要的特点。
Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。
注意该算法要求图中不存在负权边。
Dijkstra算法（迪杰斯特拉）算法是一个典型的单源最短路径算法，用于计算节点到所有其他节点的最短路径。
其主要特点是起点为中心向外扩张，直到终点到为止的扩展。
Dijkstra算法的是非常典型的最短路径算法，在很多专业中都是被作为基础的内容来进行详细的介绍，如数据结构，图论，运筹学等许多专业课程，是非常代表。
Dijkstra算法的表达方式一般有两种方式，一个为永久的和临时的标号方法，另一个用OPEN，CLOSE表方法，这里是永久和临时标号的方式。
请注意，该算法要求，负权边不准许存在图中。
1.2Dijkstra算法的资料调研分析
最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究四是采用拓扑层次编码路径视图，对最短路径进行部分实例化编码存储；五是采用并行算法，为并行计算服务。
最短路径问题一直是计算机科学，运筹学，地理信息科学与其他学科的研究热点。
大量的国内外专家和学者对这一问题进行深入研究。
经典图论和计算机数据结构和算法的不断发展，有效地结合起来，使新的最短路径算法不断涌现。
在空间的复杂性，时间复杂度和易于实施和应用领域，各有独特的地方。
目前的研究重点，一为实际应用网络的特征优化运行结构。
尽可能以统一的时间复杂度的基础上的提高算法的工作效率;二是限制网络的特征，如要求网络边缘具有证书权值，这样的方便使用基数据结构设计算法的运行结构;三是使用有损的算法，如限制搜索范围，以限制搜索的方向和限制的几何图层次第归序搜索;四为使用拓扑层次编码路径视图，一些实例化编码存储用来对最短路径进行实施;五是利用并行算法，并行计算服务。
在提高时间效率方面有较好的应用性。
其中图增长论是TQQ算法的根本，用两个FIFO队列直线了一个双端队列结构来支持搜索过程，较适合于计算单源的点到另外的所有点的之间的最短距离。
后两种算法则是基于Dijkstra算法，采用桶结构明显提高了永久标记点的搜索速度。
现在公认的最好的方法解决最短路径问题，是由E.W.Dijkstra，1959年提出的，也就是俗称的Dijkstra算法，他的名字命名的标记方法。
该算法是基于这样一种想法，一种解释的几十种不同的优化算法更好的算法TQQ（graphgrowthwithtwoqueues）,DKA（theDijkstra`algorithmimplementedwithapproximatebuckets）,DKD（theDijkstra`salgorithmimplementedwithdoublebuckets），排序的优化算法，前面的三种算法中，空间储存的问题是非常重要的，牺牲适当的时间效率，来节省空间，排序优化算法放在了一个重要的位置上，可以更好地提高时间效率。
其中TQQ算法依靠的是图增长理论，直线了两个FIFO队列与一个双
端队列结构来支持搜索过程，更适合于计算单源点到所有其他点的最短距离。
后两种算法在Dijkstra算法的基础上，使用桶结构，大大提高了对永久标记点的搜索速度。
1.3国内外主流算法及其简要展开
1.3.1A*算法
A*（A-Star）算法是最短路最有效的方式来解决一个静态的路网。
计算公式为：
F（N）=G（N）+H（N）
F（N）是节点n从初始点到目标点的估价函数，G（n）是实际成本从最初的节点到n个节点，在状态空间里，H（N）是从n到目标节点的路径的估计成本。
保证找到最短路径（最优解）的条件下，关键是要选择的评估函数H（N）：
h的估计值（N）<=n到目标节点的距离实际价值，在这种情况下，搜索点多，搜索范围变大，就会得到更低得效率。
但可以获得最佳的解决方案。
如果估计值大于实际值，搜索点少，搜索范围小，效率高，但不能保证最佳的解决方案。
估计值和实际值接近，就能获得更好的评估函数。
A*算法是一个典型的人工智能启发式搜索算法，该算法的创新，是选择下一个节点，探索引进一个已知的道路网络和目标点和当前点的距离年底评估选择下一个路径节点的基础上。
一般的A*算法可以用四个方向，八个方向，矢量网络连接，可以用来遍历路径方法的路径探讨。
城镇土地定级和评价，而不考虑道路网络，可以是一个网格八个方向法国。
A*算法可以找到任何一个因素的因素与其他各点之间的最短路径。
它不遍历整个搜索空间，但根据选定的启发式函数对最有前途的方向前进。
虽然它的搜索速度更快，理论上能够找到最佳的解决方案，但在实际应用过程中，往往由于选择不当启发式功能，往往不能找到最短路径，搜索成功率不是很高。
1.3.2遗传算法
是用来解决优化问题的搜索算法，是一种进化算法。
自然进化的生物学现象，包括基因突变，自然选择和杂交都被进化算法用来参考。
遗传算法通常作为计算机模拟实施。
为优化问题，一些数量的候选解（称为个体）抽象（所谓染色体）的种群进化为一个更好的解。
传统的二进制表示（即0和1的字符串），但也可以使用其他方法来陈述。
进化从完全随机个体的种群开始，代代发生。
在每一代，种群的适应度被评估，通过自然选择和突变产生新的生命种群，随机从目前的种群选择多个个体（根据其自身的适应度），这个种群在第一次迭代算法中，生成为当前的种群。
在遗传算法，优化问题的解被称为个人，它代表一个变量序列，称为染色体或基因的字符串。
染色体一般被表达为一个简单的字符串或数字字符串，但也适用于于特殊问题的表达方法，这个过程称为编码。
首先，算法随机生成一定数量的个体，有时操作者可以在随机生成的过程中进行干预，以提高初始种群的质量。
每一个体在每一代，都被评估并通过适应度函数的计算来得到一个适应度的数值。
个体按照适应排度序，在前面的通常是适应度高的。
“高”是指对初始群的低适应度来讲的。
下一步是产生下一代的个体组成种群。
这个过程是通过选择和繁殖，包括复制，包括交配（crossover，算法在该领域的研究，就是我们所说的交叉操作）和突变（mutation）。
选择是根据的新的个体的适应程度来执行，但在同一时间并不意味着彻底的用适应度的高低来作为标准参考，因为只是选择适应度高的个体将可能导致，算法快速收敛到局部最优解最佳的解决方案但不是全局的最有解决方案，我们称之为早熟。
作为一种妥协，根据遗传算法的原则基础上：
适应度越高，被选中的机会越高，适应低被选中的机会越低。
通过对初始数据的选择，可组成一个相对最优的群体。
然后，被选择后的个体进入交配过程。
遗传算法有交配的概率（也称为交叉概率），通常的范围是0.6至1，这个交配的概率反映了两个选定的个体交配的概率。
例如，交配概率为0.8，80％“夫妇”可以生育后代。
通过交配，每两个人产生两个新个体，而原来的“老”的个体将会被替代。
交配父母的染色体交换，导致了两个新的染色体产生，第一个个体前一半是父亲的染
色体，母亲的则是后半段，第二个人则刚好相反。
这里位置被称为是随机生成的交叉点，所指的半段并不是真正意义以上的一半。
交叉点可以是任何染色体上的位置。
下一步是突变基因突变产生新的“孩子”个体。
一般遗传算法有一个固定的突变常数（又称突变率）一般为0.1或更小，这代表了基因突变的概率。
根据这个概率，新个体的染色体随机突变通常是改变一个字节（0到1，或0的变化）的染色体。
通过（选择，交叉和变异）这一系列的过程之后，新一代的个体，从最初的一代是不同的，而且一代又一代的朝着提高适应度的方向发展，最好的人总是更要被选择产生下一代，适应度低的会逐渐被淘汰。
这个过程不断重复：
每个个体都被评估，计算每一个个体的适应度，两个个体交配和突变，产生第三代。
一遍又一遍，直到满足终止条件。
一般的终止条件有以下几种：
进化次数限制；
计算消耗的资源约束（如计算时间，计算所占用的内存）;
个体满足的最优值的条件，即已经找到最佳值;
适应已经达到饱和，继续进化不会有适应度更好的个体;
人为干预;
超过两个或两个以上的组合。
图1.3.1遗传算法的工作原理示意图
1.3.3Dijkstra算法
Dijkstra算法的基本思路是：
设置一个顶点集合S，从一个源点S到集合中定点最终最短路径的权重已经确定。
算法反复选择最短路径估计顶点i∈VS，将I并入S，I所有的出边松弛
原始的Dijkstra算法在图形数据存储和节点之间的关系和距离的计算时，基于网络的权重矩阵，形成关联矩阵，邻接矩阵和距离矩阵，需要定义n×n数组进行储存数据，其中N为网络节点，网络节点太多时，将占用大量的计算机内存。
（2）原始的Dijkstra算法的运行时一般把网络节点分为没有被标记节点，临时标记节点，永久标记节点。
网络中的所有节点初始化为未标记的节点，在搜索的过程中与最短路径的节点连接的节点为临时标记的节点，每循环从临时标记节点的路径长度最短的节点的节作为永久性标志的节点，直到找到目标节点或所有节点搜索算法结束前都将被永久标记节点。
影响了该算法的执行效率是根据算法的描述，阅历全部临时标记节点是Dijkstra算法的瓶颈。
1.4设计方案的可行性分析和预期目标
预期目标：
1.广泛收集相关资料，研究经典Dijkstra算法的主要思想及其实现
2．对目前应用于Dijkstra算法的数据结构和搜索技术进行学习研究
3.采用图的邻接矩阵或邻接表实现最短路径问题中图的存储
4．采用Dijkstra算法求从某个源点到其余各顶点的最短路径
5．将上述功能作为类的成员函数实现，编写主函数测试上述功能
6.以C#作为开发工具实现改进最短路径算法的代码编制，完成算法的实现
可行性分析：
1.技术可行性
个人能力方面：
有一定的专业知识，技术能力，了解行业背景，有相应的资料
个人环境方面：
又上网条件，有充足的相关资料和书籍，可以获得充分的研究资源
软件方面：
C#，它具有简单，面向过程，稳定，与平台无关，解释型，多线程，动态等特点，因此将其作为首选工具。
由于所需要的硬件配置要求不高，对于代码编制，和算法的实现都是非常合适的。
所以完全具备设计方案所需要的软件条件。
2.经济可行性无经济方面问题
3.法律可行性相关软件都是正版，独立自主开发
1.5本文主要研究内容
根据Dijkstra算法，用C#语言进行编译，使软件可以实现查询最短路径的功能。
主要研究并实现以下内容功能：
1加载、更换地图，并可以在地图上标注大量节点，使之连接成各个路线，提供大量路线选择方案
2选择任意起点和终点，只需要查询起点和终点间的最短路径，便可快速计算出之间的最短距离，挑选最短的路线
3添加数据库，实现储存、加载数据的功能，使先前的操作得到保留并可以随时调用
第二章Dijkstra经典算法的研究
2.1Dijkstra算法原理
EW提出的Dijkstra算法图表理论，一个众所周知的最短路径算法Dijkstra算法是在1959年设计的，使用的数字点到其他顶点的最短路径可以得到。
原始Dijkstra算法的网络节点分为三个部分：
未标记节点，临时标记的节点和永久标记的节点。
网络中的所有节点启动的第一个节点未标记的节点，在搜索的过程当中，与最短路径中的结点相互连通的结点为临时标记结点，每个周期的循环全部是从临时标记节点的最短的路径长度作为永久纪节点，直到找到目标节点或所有节点成为永久标记节点算法结束。
假设每个人都有一个标签（WJ，PJ），其中WJ是最短路径长度S从起源点到j点（从顶点的最短路径本身是零路（没有弧的道路），其长度等于零）;PJJJ是从s到前一个点的最短路径。
求解从起源点到j点的小号的基本过程，最短路径算法如下：
1）初始化。
原点设置：
①WS=0，PS是空的;②其他点：
WI=∞，PI=？
（3）标记的起源点S，设ķ=S，所有其他点设置未标记
2）标记的点k到其直接连接的测试未标记点j的距离，并设置：
WJ=MIN{WJ周DKJ}的类型，DKJ点k的直接连接距离J.
3）选择下一个点。
从所有未标记的节点，选择WJ最小的一个I：
WI=MINWJ，I点选择为的最短路径点，并设置为已标记.
4）找到I的第一点。
从标记点中，找到点I直接连接的点j*，作为前点，设：
I=J*。
5）标记点I。
如果所有点已标记，该算法将彻底计算出来，否则，记为K=I，转到2）继续。
Dijkstra算法最短路径应用演示
图2.1.1Dijkstra算法最短路径应用演示图
图2.1.2从0节点到4节点的最短路径
2.2Dijkstra算法的仿真实现
根据上面的理论与思想，本文使用Microsoft公司的visualstudio2008软件，visualC#语言，Access数据库编写，制作以Dijkstra算法为基础的可以查询最短路径的软件，使最短路径搜索查询的功能得到了实现。
以下是用到的一段Dijkstra算法的关键的代码：
privatevoidShortestDist（ints）
{
for（inti=0;i{//dist和path数组初始化
dist[i]=Da.Edge1[s,i];//邻接矩阵第s行元素赋值到dist中
S[i]=0;//已求出最短路径的顶点集合初始化
if（i!
=s&&dist[i]{
path[i]=s;
}
elsepath[i]=-1;//路径存放数组初始化
}
S[s]=1;//顶点s加入顶点集合
dist[s]=0;
/*循环计算该场所与邻接场所之间的最短距离*/
for（inti=0;i{//从顶点s确定n-1条路径
doublemin=Da.Uplimit;
intu=s;
for（intj=0;j{//选择当前不在集合S中具有最短路径的顶点u
/*如果有路径比目前的最小值还小，则替换这个最小值*/
if（S[j]==0&&dist[j]{
u=j;
min=dist[j];
}
}
S[u]=1;//将顶点u加入集合S，表示它已在最短路径上
for（intw=0;w{//修改
if（S[w]==0&&Da.Edge1[u,w]{
dist[w]=dist[u]+Da.Edge1[u,w];
path[w]=u;
}
}
}
}
publicvoidgetdata（ints,inte）
{
D[0]=e;
intk;
for（k=0;D[k]!
=s;k++）
{
if（D[k]==-1）
{
MessageBox.Show（"抱歉，没有找到通路"）;
return;
}
D[k+1]=path[D[k]];
}
if（S[e]!
=0）
{
for（;k!
=-1;k--）
{
listline=listline+Da.Tb.Rows[D[k]]["nname"].ToString（）+"-";
lstLine.Add（D[k]）;
if（lstLine.Count>=2）
{
length=length+Da.Edge1[LstLine.Count-1,LstLine.Count-2];
}
}
}
else
{
//没有路径
}
this.Refresh（）;
}
第3章软件开发、设计工具简介
3.1C#语言开发软件工具
3.1.1简介
Csharp（音标[∫a:
p]）（又被简称为"C#"）是微软公司在2000年6月发布的一种新的编程语言，并定于在微软职业开发者论坛（PDC）上登台亮相。
C#是微软公司研究员AndersHejlsberg的最新成果。
C#看起来与Java有着惊人的相似；它包括了诸如单一继承、界面、与Java几乎同样的语法，和编译成中间代码再运行的过程。
但是C#与Java有着明显的不同，它借鉴了Delphi的一个特点，与COM（组件对象模型）是直接集成的，而且它是微软公司.NETwindows网络框架的主角。
在本文中，我将考察创建一种新计算机语言的一般动机，并将特别指明是什么原因导致了C#的出现，然后我将介绍C#和它与Java、C、C++的相似之处。
其次我将讨论一些存在于Java和C#之间的高层次的和基础的差别。
我将以衡量在用多种语言开发大型应用程序的时候所需的知识（或者对这种知识的缺乏程度）来结束本文，而这正是.NET和C#的一个主要战略。
目前，C#和.NET还只能以C#语言规则，以及Windows2000的一个“d预览版本”，还有MSDN上迅速增多的文档集子的形式获得（还没有最终定型）。
3.1.2定义
微软C#语言定义主要是从C和C++继承而来的，而且语言中的许多元素也反映了这一点。
C#在设计者从C++继承的可选选项方面比JAVA要广泛一些（比如说struts），它还增加了自己新的特点（比方说源代码版本定义）。
但它还太不成熟，目前不可能挤垮JAVA。
C#还需要进化成一种开发者能够接受和采用的语言。
而微软当前为它的这种新语言大造声势也是值得注意的。
目前大家的反应是：
“这是对JAVA的反击”。
C#更像JAVA一些，虽然微软在这个问题上保持沉默。
这也是意料中的事情，因为JAVA近来很成功而使用JAVA的公司都报告说它们在生产效率上比C++获得了提高。
JAVA所带来的巨大影响和大家对它的广泛接受已经由工作于这种语言和平台之上的程序员数量明显的说明了（估计世界范围内共有两百五十万程序员使用JAVA）。
由这种语言写成的应用程序的数量是令人惊讶的并已经渗透了每一个级别的计算，包括无线计算和移动电话（比如日本发明的JAVA电话）。
C#能够在用户领域获得这样的礼遇吗?
我们必须等待并观望，就象已经由SSI公司的CEO和主席KALPATHIS.SURESH指出来的那样：
“我发现所有这些都是渐进的。
如果C#不存在，我们总能回到JAVA或C和C++。
这些都不完全是新技术，它们在更大的意义上来说只是大公司制造的市场噱头。
我们必须给他们时间安顿下来看看这些是不是真的对IT工业有什么影响。
” C#（CSHARP）是微软对这一问题的解决方案。
C#是一种最新的、面向对象的编程语言。
它使得程序员可以快速地编写各种基于MICROSOFT.NET平台的应用程序，MICROSOFT.NET提供了一系列的工具和服务来最大程度地开发利用计算与通讯领域。
正是由于C#面向对象的卓越设计，使它成为构建各类组件的理想之选——无论是高级的商业对象还是系统级的应用程序。
使用简单的C#语言结构，这些组件可以方便的转化为XML网络服务，从而使它们可以由任何语言在任何操作系统上通过INTERNET进行调用。
最重要的是，C#使得C++程序员可以高效的开发程序，而绝不损失C/C++原有的强大的功能。
因为这种继承关系，C#与C/C++具有极大的相似性，熟悉类似语言的开发者可以很快的转向C#。
3.1.3从Java继承而来的特点
结构形式
类：
在C#中类的声明与Java很相似，这是合理的，因为经验告诉我们Java模型工作得很好。
Java的关键字import已经被替换成using，
升级会员 