计算机毕业论文,毕业论文,毕业设计 毕业论文免费检测 知网论文检测

基于Dijkstra最短路径算法-毕业论文

时间:2011-12-22 11:11来源: 骆驼毕业论文网 作者:admin
摘要 单源路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。传统的单源路径算法主要有Floyd算法和Dijkstra算法。Floyd算法用于计算所有节点之间的单源路径。Dijkstra算法则用于计算一个节点到其他所有节点的单源路

QQ交谈计算机毕业设计,毕业设计,毕业论文,计算机毕业论文

摘要
单源路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。传统的单源路径算法主要有Floyd算法和Dijkstra算法。Floyd算法用于计算所有节点之间的单源路径。Dijkstra算法则用于计算一个节点到其他所有节点的单源路径。Dijkstra算法是已经证明的能得出单源路径的最优解,但它的效率是一个很大的问题。对于具有n个节点的一个图,计算一个节点到图中其余节点单源路径的算法时间复杂度为O(n2)。对于一座大中型城市,地理节点数目可能达到几万个到几十万个,计算单源路径的时间开销将是非常巨大的。
论文组织如下:首先阐述了该系统研究现状和以后的可能性;其次介绍了相关的开发工具及技术基础;接着对系统的需求进行了分析,并提出了具体的设计方案;然后展现了整个系统的具体实现,各功能模块的实现;最后对该软件进行了严格的测试。
关键字: C++,B/S,迪杰斯特拉
目录
第一章 绪论 4
1.1 最短路径问题介绍 4
1.2 最短路径算法介绍 4
第二章 系统技术方法研究 6
2.1 系统算法——dijkstra 6
2.2 新算法——层次图模型算法 7
2.3 dijkstra和层次图模型 7
2.4 算法思想 10
第三章 总体设计 12
3.1 设计的总目标 12
3.1.1.目标概况 12
3.1.2. 功能划分和描述 12
3.2 系统平台环境: 15
3.2.1硬件平台: 15
3.2.2 软件平台: 15
3.3 编程语言:C++ 15
第四章  系统设计 17
4.1 系统工作流程 17
4.1.1 算法初始化流程 17
4.1.2 用户控制流程 17
4.1.3 计算路径流程 18
4.2 系统整体结构与模块划分 19
第五章 详细设计 20
5.1dijkstra算法分析 20
5.2 各模块详细设计 21
5.2.1 初始化详细设计 21
5.2.2 执行算法 23
5.2.3 算法运行 24
第6章 系统测试 25
6.1 软件测试 25
6.1.1 软件测试概述 25
6.1.2 测试步骤 25
6.2 系统维护 26
第七章 系统维护和改进 26
7.1 系统优点 26
7.2 系统的改进与提高 26
7.2.1 系统优势 26
7.2.2 系统不足 27
7.3 结论 27
参考文献 28

5.在子图GS中利用Dijkstra算法计算vi和vj之间的最短路径。
在基于层次图模型的算法中,子图的划分是一个重要的问题。计算机毕业论文,考虑到城市交通网的一些特点,基于层次图模型的算法对于城市布局较为分散,城市主要区域之间有主干道连接的城市尤为适宜。在实际划分中,可以把城市中地理位置相对集中的区域划分为一个子图,这种思想与人在查找最短路径的思想类似。
城市交通诱导系统中的最短路径并非一定指地理上的最短,不同的人在不同的情况下,要求的最短路径时不同的,可能是时间最短,也可能是费用最少或者地理位置上的最短。在基于层次图模型的最短路径算法中,图中边的权重也相应地可以是时间代价、费用代价或地理距离代价。对于时间代价或费用代价,计算机毕业设计,图中边的权重将随交通流量的变化而变化。在设置了城市交通流量检测装置的城市交通诱导系统重,可以定期地重新计算子图之间的阻抗函数,以适应交通流量的变化。在这种情况下,得到的最短路径是一个动态的最短路径。因此基于层次图模型的最短路径算法可用于动态交通诱导系统。基于层次图模型的最短路径算法实际上是一种有损算法,它并不能保证每次计算一定能够得到最精确的最短路径,但在大多数情况下均可得到较精确的最短路径。
5.2.2 执行算法
 此界面接收用户的输入,并且进行Dijkstra算法操作。运行的过程是:输入源结点(默认为0)——〉处理层保存——〉接收用户输入权值——〉处理层接收保存——〉根据保存输入参数运行Dijkstra算法——〉对过程参数保存——〉显示结果。用户可以根据图形进行输入。

(部分主要代码插此)

系统在按钮控件command1(运行按钮)的事件中call Dijkstra()算法,调用子程序Dijkstra,对用户输入的数据进行处理,系统必须在command1的触发情况下才能运行算法才能对结果量进行动态的输出。在本系统中,command2(下一步按钮)按钮在command1的时间触发情况下才能显示,而command1控件自动隐藏。在按下command1的同时系统自动为其下一个界面的输出参数赋相关值。
 


 

 

本文内容只是论文部分简介,如需了解更多详情请咨询本站客服! QQ交谈计算机毕业设计,毕业设计,工程硕士论文,计算机毕业论文
毕业论文搜集整理:毕业论文网 计算机毕业设计 计算机毕业论文 毕业设计


顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
计算机毕业设计
计算机毕业论文
论文发表