摘要
针对智能交通网络系统的快速查询需求展开研究。对基于Dijkstra最短路径算法在受限制二维空间网络的应用局限性进行分析的基础上,提出了网络分层级算法基本概念和算法路线。研究结果表明,采用分层级网络算法,可以将一个复杂度为O(n2)的网络路径算法问题转化为一个复杂度为O(k×103)的简单问题。最后,通过结合具体案例进行了仿真实验,证明了网络分层级算法的优越性和实用性。
To meet the demand of fast inquires about intelligent transportation network system,based on analysis of limitations in application of Dijkstra-based shortest path algorithm to restricted two-dimensional space network,the basic concept and route of network hierarchical algorithm is put forward.The research results indicate that the hierarchical level network algorithm can transfer a network path algorithm problem with the complexity of O（n2） into a simple problem with the complexity of O（k×103）.Simulation experiment on specific cases proves the superiority and practicability of network hierarchical algorithm.
出处
《北京信息科技大学学报（自然科学版）》
2012年第6期18-21,共4页
Journal of Beijing Information Science and Technology University
基金
北京市教育委员会科技计划面上项目(71E1010912)
关键词
最短路径
受限制二维空间网络
网络分层级算法
the shortest path
restricted two-dimensional space network
network hierarchical algorithm
