| 基于社区分析的最短路径计算 |
| |
| 引用本文： | 马明全,周明全,耿国华,康宝生. 基于社区分析的最短路径计算[J]. 计算机应用与软件, 2008, 25(4): 177-181 |
| |
| 作者姓名： | 马明全 周明全 耿国华 康宝生 |
| |
| 作者单位： | 西北大学计算机系,陕西,西安,710069;西安邮电学院计算机系,陕西,西安,710062;北京师范大学信息学院,北京,100875;西北大学计算机系,陕西,西安,710069 |
| |
| 摘 要： | 具有城市规模的大规模交通网络作为大规模网络的一个应用领域,由于不断升级的交通紧张问题,近年来也成为一个热点研究领域.智能交通领域中,在进行动态交通分配时,需要快速计算当前路况状态下的最短路径,因此大规模网络中最短路径的算法研究具有相当重要的现实意义,但由于网络规模因素,最短路径计算非常耗费资源.在社区分析的基础上,对大规模网络进行分割及简约,并提出了一个切实可行的最短路径的并行算法,并对该算法的正确性和时间复杂度进行了分析,理论分析及实验结果均表明:本算法在大规模网络应用中明显优于单纯应用迪杰斯特拉算法以及LC-2q并行算法,具有良好的实用性.
|
| 关 键 词： | 大规模网络 社区 网络分割 最短路径 |
| 修稿时间： | 2006-06-20 |
STUDY ON NETWORK PARTITION AND SHORTEST PATH BASED UPON COMMUNITY ANALYSIS |
| |
| Ma Mingquan,Zhou Mingquan,Geng Guohua,Kang Baosheng. STUDY ON NETWORK PARTITION AND SHORTEST PATH BASED UPON COMMUNITY ANALYSIS[J]. Computer Applications and Software, 2008, 25(4): 177-181 |
| |
| Authors: | Ma Mingquan Zhou Mingquan Geng Guohua Kang Baosheng |
| |
| Affiliation: | Ma Mingquan1,2,Zhou Mingquan3 Geng Guohua1 Kang Baosheng11(Department of Computer Science,Northwest University,Xi'an 710069,Shaanxi,China)2(Department of Computer Science,Xi'an Post , TeleCommunication College,Xi'an 710062,China)3(College of Information,Beijing Normal University,Beijing 100875,China) |
| |
| Abstract: | The traffic network with city size,as an application of large-scale network,nowdays attracts much interests due to the increasing pressure of urban traffic.In ITS,in order to assign traffic flow dynamically,it's required to calculate shortest path immediately.So calculation of shortest path in large-scale network has great practical significance.However,because of the scale of network,the calculation is rather costly.Based on community analysis,the large-scale network is partitioned and simplified,and a bra... |
| |
| Keywords: | Large-scale network Community Network partition Shortest path |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
