基于GIS系统的最短路径问题研究

来源 :中国地质大学(武汉) | 被引量 : 0次 | 上传用户:yangl3255
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文对最短路径算法的优化及实现过程进行了研究。文章提出了一种方便的解决方案,在内存中开辟数组,将数组的下标与某结点点号相对应,可以快速计算出该结点的出度,从而通过弧段起点数组和弧段终点数组的对应关系可以找到该结点的邻接点。最后,在对Dijkstra算法的实现过程中,对其中的一个关键步骤——搜索最小权值的顶点进行了优化,针对快速排序算法的不稳定性,提出了改进的搜索方案,使用折半插入排序函数对最短路径值数组重新进行地址排序,以减少查找次数,提高排序的效率。可使排序的平均时间复杂度从O(n<2>)降低到O(n)。通过对优化算法的评价,表明了本文提出的优化算法是高效率的。
其他文献
本文首先对无线传感器网络的体系结构、传感器节点结构以及无线传感器网络区别于传统网络的特性做了简单的描述,分析了无线传感器网络所面临的安全威胁,探讨了无线传感器网络协
在集成电路技术发展的初期,电路工作速度较低、器件特征尺寸尚未达到深亚微米级,门延时远远大于互连线延时,可以将互连线看作是一种仅仅具有电气连通作用的理想金属导体,忽略
随着嵌入式系统、网络技术与自动控制技术的发展与成熟,信息物理融合系统(Cyber Physical System,CPS)这一术语被提出,被视为继计算机,互联网之后的又一重要里程碑。CPS在结构与
随着互联网和信息化技术的蓬勃发展,包括网页文档和其他数字化资源在内的各类信息库和知识库的规模也在飞速增长,这对负责管理和检索这些文档集合的系统(其中最典型例子就是搜索
图片文字检测是文字识别过程的重要步骤,对它进行研究有着重要的理论和应用价值。在本文中,我们提出了以边缘纹理作为检测文字的主要特征。提取出图像的边缘纹理后,我们初始的系
学位
音频工作站系统是数字音频技术和计算机网络技术相结合的产物,它改变了广播电台延用了几十年的传统工作方式,结束了以模拟磁带为记录载体,借助于剪刀和胶带以手工方式进行节目编
学位
近年来,Internet已成为一种主流的软件运行环境。与传统的软件运行环境相比,Internet具有开放、动态、难控的特点,其上应用需求也多样而易变。如何协同Internet环境中的各种资源
随着世界经济的迅速发展和科学技术的不断进步,物流对经济贸易活动的影响与日俱增,受到越来越多人们的关注。在中国,越来越多的人们已经意识到物流对企业发展的重要性,因为物流业
学位
时间是自然界无所不在的客观属性。时态数据库将时间作为数据的属性纳入系统的管理范畴,可以存储和管理多个时间状态数据。邮政综合服务平台采用现代技术和理念,实现了应用系统