A SURVEY ON HOP-CONSTRAINED SHORTEST PATH PROBLEM AND AN IMPROVED ALGORITHM

摘要：

This paper presents a survey on the Hopconstrained Shortest Path (HSP) problem.And a modified algorithm is proposed by analyzing the features of the optimal solution of the HSP problem.We apply bidirectional breadth-first search strategy to this algorithm, and try to reduce the number of vertices and edges involved in the computational process so as to reduce computing time.And the experimental results show the effectiveness of the proposed algorithm for large-scale network with fewer hops (around 6).

关键词： Hop-constrained Shortest Path HSP Bidirectional breadth-first search

作者: QINGAN FANG JUN HAN LIYONG MAO ZHAOGUO LI

作者单位: School of Computer Science & Engineering,Beihang University,Beijing,China

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer Technology and Development(2011第三届计算机技术与发展国际会议 ICCTD2011)

会议地点: 成都

会议语种:英文

页码: 49-53

在线出版日期: 2011-11-25（万方平台首次上网日期，不代表论文的发表时间）