资源描述：
《基于gis的城市道路网最短路径算法探讨》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第 卷第 期计算机学报 年 月 基于的城市道路网最短路径算法探讨严寒冰刘迎春 浙江工程学院电子与自动化系杭州 摘要文中从城市道路网络的特点出发#分析了道路路段间的连通关系#得出一种求城市道路网络两节点间的最短路径的算法算法的复杂度与网络节点数)成线性关系#即* ) 最后通过在&软件+,-
2、.中编制的算法程序实例#验证了算法的实用性和可靠性关键词最短路径#城市道路网络#&#算法中图法分类号 /012/3456789:;56<7=>7=49568?@87=AB78CDEF5A>018GAE1>5=H1?9=5354CIJ+-!KL-MNIL-M!OP- QRSTUVWRXVYZ[R]VUYX^]_TX‘abVYWTV^YX#cdRe^TXfgX_V^VbVRYZh]^RX]RTX‘iR]dXYYfj#kTXfldYb /mE86A?8OLn+opLq
3、rLnqPnnn+-s+MoLpOtsOLqOMpnpOnOopnp,+pOps-ps,L-pnL-+qLpuDno+r-pOLn+MoLpOtLn+nr-pOMMo+,OLqov+-qo+pL-nOL,+!t-Mo+rnL-pOo+r-pO,on-pr+MoLpOtDnqt,wLpuLnxPnp,o,opL-ppO-Pt!o.-rnL-pOo+r-psOLq-v-pL-+nO
4、opqPp+MoLpOtDnqt,wLpuLn,o,opL-ppO,so.pO-Pto.-rnJppO-r.pO+opLq#Lp,ovLrnntL-np+-qsOLqO,ovpO+ppO+MoLpOtLn+,,Lr+-roL+y1C256>EnOopqPp#qLpuDno+r-p#&#+oLpOtpLq+MoLpOt 在求解时都有可能准备搜索所有的网络z引言节点#在网络节点数较大情况下#其算法的时间花费成倍甚
5、至幂次增长#很难满足实际运算的需要通常的最短路径算法#往往是建立在抽象的数本文在对城市道路网络进行大量分析%实验的学模型之上#即网络模型在这种网络模型上#实际基础上{
6、#认为过于抽象的网络模型忽略了道路网的路径被抽象为网络中的一条边#实际路径的长度络中某些内在的拓扑信息#如边之间的相对位置关与网络边的长度可以不成比例#以边的权值来表征系等在对道路网络进行一定数学抽象的基础上#建路径的长度 或其它特征 #在该网络上求某点到其立了一个基于地理相对关系的数学模型#提出了几种它任一点的最短路径的方法#被称为最短路
7、径算较优的求城市道路网络最短路径算法#适用于不同的法最短路径问题{
8、在数学中被认为是问题#各求解条件通过算法检验{
9、#给出了算法的时间花费#种算法即使是较优的狄克斯特累算法 }Lx~npo+Dn并在实际应用中证明了算法的实用性和可靠性收稿日期 ! ! "修改稿收到日期 ! ! 严寒冰#女# $年生#获博士学位#副教授#目前主要研究方向为图像处理%&应用和多媒体教学刘迎春#女# ’(年生#获硕士学位#助教#研究方向为&应用%数据库技术#现在浙江工业大学工作期严寒冰等基于9
10、:的城市道路网最短路径算法探讨城市交通网络的节点和边即地图中的路段交叉点 模型的建立和路段网络中节点和边的拓扑关系通过节点和边的属性字段值来定义即在节点的属性字段中有相城市交通枢纽主要由街道和河流组成但重点交边的信息以及节点的相对地理坐标在为街道的集合交通图主要由众多街道相交相连而边的属性字段中有边的起止节点的信息以及该边构成并组成纵横交织错综复杂的城市交通网络的权值如长度这些属性值的赋予可通过 编程实现在图在交通网络图中街道间的地理位置关
11、系相当复的编程语言 杂一条街道可能与若干条街道相交相连且其相中打开地图窗口即可看到一张清晰的城市交通电交相连的模式复杂为了避免过多地考虑街道间的子地图拓扑关系在本文中抽取交通网络图中街道交叉路口作为分析的对象之一并对分析的另一对象 准备算法求最短路径的最差解街道以交叉路口为点进行分割成为路段这样整!"#$%&’"!()
