基于社区分析的最短路径计算

• 作者: 周明全 康宝生 耿国华 马明全
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 大规模网络 社区 网络分割 最短路径
• 年，卷（期）: 2008,（4）
• 所属期刊栏目: 网络与通信
• 页码范围: 177-181
• 页数: 5页
• 分类号: TP3
• 字数: 5095字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2008.04.068

摘要

具有城市规模的大规模交通网络作为大规模网络的一个应用领域,由于不断升级的交通紧张问题,近年来也成为一个热点研究领域.智能交通领域中,在进行动态交通分配时,需要快速计算当前路况状态下的最短路径,因此大规模网络中最短路径的算法研究具有相当重要的现实意义,但由于网络规模因素,最短路径计算非常耗费资源.在社区分析的基础上,对大规模网络进行分割及简约,并提出了一个切实可行的最短路径的并行算法,并对该算法的正确性和时间复杂度进行了分析,理论分析及实验结果均表明:本算法在大规模网络应用中明显优于单纯应用迪杰斯特拉算法以及LC-2q并行算法,具有良好的实用性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	康宝生	西北大学计算机系	119	953	15.0	23.0
2	耿国华	西北大学计算机系	497	5986	35.0	55.0
3	周明全	北京师范大学信息学院	270	2127	22.0	27.0
4	马明全	西北大学计算机系	5	27	3.0	5.0