文档介绍：盗镜己较低持凶钣怕肪端惴ā�北京白颐路��蒋捷。①北京理工大学计算机系��一�〉乩硇畔⒅行�北京紫竹院百胜村��。并且随着人口和车辆的持续增长,在城市中尤其是大城市中由于交通拥挤而造成的损失也在逐年增加,单纯的增加交通系统中道路的基础设施的建设已经不能从根本上解决交通系统中存在的这些问题。自本世纪六十年代以来,��、全球定位系统���偷乩硇畔⑾低���构成的空间信息高技术群,其为交通系统中这些根本问题的解决提供了有利的工具,��翟氐己较低骋殉�为解决交通系统问题的最有效的方法之一。作为���抵械男滦肆α浚珿�车载导航系统一经问世就显示出强大的生命力和广阔的应用前景,并已经产生了巨大的社会和经济效益。在当前商业化��翟氐己较低持校�刂菲ヅ洹⒌赝计ヅ洹⒆钣怕肪斗治觥⒙肪吨改稀�信息服务是系统最主要的技术水平标志�艽浩剑���。尤其最优路径分析是��翟氐己�系统中最基本、最关键的问题,它直接决定了��翟氐己较低车纳��Α=煌ㄍ�缰械淖�优路径分析不但可以指在一般地理意义上的晟短路径问题,而且也包括在其他量度方面上的延伸,如时间、费用、线路流量等,相应的最优路径分析则应转换成为最快路径问题、最低费用问题、晟小流量问题。相比较于一般意义上的网络,交通网络具有许多独有的特征。现有的很多��翟氐己较低持械淖钣怕肪斗治鏊惴ǎ�皇谴右话阃�绲耐仄私峁狗治龀龇ⅲ�没有密切结合现实交通网络的具体特征,因此在表达、管理和查询交通网络关系时必然存在着缺陷,。��翟�导航系统需要在现实交通环境中实时应用,因而其最优路径分析算法必须高效。本文作者针对城市��盗镜己轿侍猓�紫确治鼍�渥钣怕肪端惴ǖ乃枷耄�芯肯钟懈�种最优路径算法的实现方法及数据结构。在此基础上,提出了城市��盗镜己绞�菽P汀�数据结构,并发展了用于城市��盗镜己降某鞘械缆方煌ㄍ�缱钣怕肪端惴ā1疚牡�节主要介绍经典最短路径算法的思想以及现有最短路径算法的实现方法,第�诮樯茏髡咛岢�韩刚。关心的焦点,,研究适合交通网络特征的教据模型和数据结构,并在此基础上提出了高效的��嵩氐己�系统最优路径分析算法.����摘要:随着��嵩氐己较低逞芯康娜涨魃钊耄�佑谙低宠裥牟糠值耐�绶治鲆踩找娉晌H嗣�关键词:交通网络最优路径分析��荡鞯己较低����●奉研究受国家自拣科学基金资助�嗪�����
馗床僮��、��瞡一�危�纱饲蟮么�,到图上其余各项点得各最短路径使免算法在某几个点之间陷入死循环的状态。在实际实现算法的过程中通常采用标记法来区分的��盗镜己阶钣怕肪端惴ǎ��节给出结论与建议。���涞淖疃搪肪端惴ḿ捌涫迪址椒�不管对最优路径算法采取那一种度量标准,即不管是最短路径、最低费用还是鼓小流量,归根结底它们的核心算法都是最短路径算法。����算法、���惴ā�木算法等几个经典最短路径算法是当前��翟氐己较低持凶疃搪肪端惴ǖ睦砺刍�。�绕銬����惴ū�大多数��翟氐己较低乘�捎茫�皇遣煌�己较低吃谑迪炙惴ㄊ辈捎昧瞬煌�氖�萁峁埂���.����算法的基本思想:����算法的基本思想是�衔得簟⑽馕懊瘢���:��偕栌么�ǖ牧诮泳卣骳��幢硎敬�ㄓ邢蛲迹瓹���琂�硎净�����上的权值����#�,�不存在,则置���,,�琞为一。�R颜业酱觱出发的最短路径的终点的集合,它的初始状态为空集。那么,从、,出发到图上其余各顶点�盏���赡艽锏降淖疃搪肪冻ざ鹊某踔滴#篸������������琲���≡:��������������褪堑鼻扒蟮玫靡惶醮�,出发得最短路径的终点。令������薷拇�,出发到集合�猄上任一顶点,∽可达的最短路径长度。如果则修改����猟�����������琸�依路径长度递增得序列。由以上的算法流程可以看出,整个算法的规模可以记作��������凑�鍪奔涓丛�度是������.计算过程中的标记方法交通网络中各节点之间的复杂的相互关联造成了交通的复杂性。算法在访问某个节点之后,有可能会直接反向回到该节点或沿着某条路径回到该节点,因此必须建立一种机制以避每个访问过的点�盅艄ńㄑ牛���。大多数标记方法每个节点通常包含三条信息,即点的状态��、父节点��、距离��。其中距离��代表了在遍历过程中从源节点�,��代表从�絠的唯一最短距离。父节点��代表了当前情况下最短路径树上直接先于�慕�点。状态��是以下三种中的一种:来到达的������⒘偈北昙堑�������和永久标