摘要
在总结公交网络特点的基础上,提出了运用“燃烧”算法来计算公共交通系统的最优路径算法。并用一个简化的例子来说明这种算法的流程,最后结合北京公交网络的一些数据,对这种算法以及经典的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.
出处
《海洋测绘》
2005年第6期41-44,共4页
Hydrographic Surveying and Charting
基金
北京市重点实验室共建项目(SYS10001402)
关键词
地理信息系统
最优路径
最短路径
公交网络
最少换乘
geographic information system
best path
shortest path
public traffic network
least transfer
