基于城市道路网的最短路径分析解决方案刘云翔陈荦李军陈宏盛(国防科技大学电子科学与工程学院,湖南长沙410073)摘要:近年来GIS对网络分析功能的需求迅速增长.网络分析中的一个关键问题是最短路径问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位.由于最短路径分析常用于汽车导航系统以及各种城市应急系统(如110报警、119火警以及120急救系统),本文针对城市道路网的特点,提出了一种实用、高效的最短路径分析解决方案.关键词:最短路径;Dijkstra算法;城市道路网:TP391.4文献标识码:A:10001220(2003)07139004AnImplementationoftheShortestPathAnalysisBasedonCityRoadNetwork2,2LIUYunXiang,CHENLuo,LIJunCHENHongSheng(SchoolofElectronicScienceandEngineering,NationalUniversityofDefenseTechnology,Changsha410073,China)AbstractInrecentyears,NetworkanalyseshavebecomemoreandmoreimportantinGIS.Asthekeyproblemof2networkanalyses,computingshortestpathsoveranetworkhasbecomeanimportanttaskinmanynetworkandtransportationrelatedanalyses.Shortestpathanalysisisoftenusedinvehiclenavigationsystem2andcityemergencysystems.Thispaperintroducesapracticalandefficientrealizationofshortestpathanalysisaccordingtothecharacteristics22ofcityroadnetwork.Werunouralgorithmonamiddlerangepersonalcomputerwithrelativelylargedataset.Theexperimentalresultisverypromising,thusprovestheefficiencyoftheproposedalgorithm.22Keywordsshortestpath;dijkstraalgorithms;roadnetwork2---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---1引言近年来由于普遍使用GIS管理大型网状设施(如城市中的道路网、各类地下管线、通讯线路等),使得对网络分析功能的需求迅速增长.通用的网络分析功能包括路径分析、资源分配、连通分析、流分析等.网络分析中最基本的问题是最短路径问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位.从网络模型的角度看,最短路径分析就是在指定网络中两结点间找一条阻碍强度最小的路径.根据阻碍强度的不同定义,最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等.由于最短路径问题在实际中常用于汽车导航系统以及各种城市应急系统等(如110报警、119火警以及120急救系统),本文对基于城市道路网的最短路径分析进行了深入研究.2实现机制要对城市道路网进行最短路径分析,首先必须将现实中的城市道路网络实体抽象化为网络图论理论中的网络图,然后通过图论中的网络分析理论来实现道路网络的最短路径分析.在实际应用中,城市道路网的表现形式一般为数字化的矢量地图,其网络空间特征中的交叉路口坐标和道路位置坐标是在地图上借助图形来识别和解释的;而为了能够高效率地进行最短路径分析,必须首先将其按结点和弧的关系抽象为图的结构.这就需要先对原始道路图进行预处理,建立其相应的网络拓扑关系.预处理的工作主要包括:·对原始的道路图进行线元素的拓扑检查、进行剪断处理,生成线和线相互不相交叉的道路图;·对剪断后的道路图创建拓扑关系,并定义其属性特征,如道路名称、道路距离、交通流量等;·生成有拓扑关系的拓扑文件.经过预处理后,最短路径分析算法直接从拓扑文件中提取道路网的网络拓扑结构并加载到内存中,从而提高路径分析的效率.如果由于城市建设的快速发展,城市道路发生了变化,地图更新后,只需重新进行预处理生成拓扑文件.系统的整个工作流程见图1.要实现这样的系统主要需解决两个关键问题:(1)如何用地图表示城市道路网以及提取网络拓扑结构;收稿日期:2001208224作者简介:刘云翔,硕士研究生,主要研究领域为地理信息系统与数据库技术.李军,博士,讲师,主要研究领域为地理信息系统与信息可视化技术.陈宏盛,硕士,副教授,主要研究领域为人工智能与数据库.陈荦,硕士,讲师,主要研究领域为地理信息系统与数据库技术.©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.---本文来源于网络，仅供参考，勿照抄，如...