一种公共交通的最优路径算法  

Best-routing Algorithm for Public Traffic System

作　　者：沈雷[1] 张鑫[2] 马福诚[3] 

机构地区：[1]解放军信息工程大学测绘学院,河南郑州450052 [2]北京大学遥感与地理信息系统研究所,北京100871 [3]海军海洋测绘研究所,天津300061

出　　处：《海洋测绘》2005年第6期41-44,共4页Hydrographic Surveying and Charting

基　　金：北京市重点实验室共建项目(SYS10001402)

摘　　要：在总结公交网络特点的基础上,提出了运用“燃烧”算法来计算公共交通系统的最优路径算法。并用一个简化的例子来说明这种算法的流程,最后结合北京公交网络的一些数据,对这种算法以及经典的D ijkstra算法做了几点比较,无论在空间还是时间复杂度上这种算法都大大优于D ijkstra算法。This paper first presents a best routing “burning” algorithm for public traffic system on the basis of analyzing the unique character of urban traffic network. Then a simple numerical example is given, which shows the flow of the algorithm. Finally, it is compared with the classic Dijkstra algorithm by using the data of Beijing traffic network. The algorithm is much more efficient both in space and time complexity than Dijkstra algorithm.

关 键 词：地理信息系统 最优路径 最短路径 公交网络 最少换乘 

分 类 号：P208[天文地球—地图制图学与地理信息工程]