计算图上两点间的最短路径问题是计算机学科里一个经典问题，在许多问题中有着重要应用, 如物流规划、交通模拟、行车导航、社交网络等。随着应用需求和信息技术的发展，对于求解最短路径问题提出了新的要求。这些要求体现在以下三个方面：(1) 大规模图数据处理；(2) 图数据的动态性；(3) 计算的实时性要求。本项目针对最短路径问题求解的最新需求，结合并行计算平台的发展，在并行计算的系统平台上（包含共享存储的多核系统、分布存储的机群系统），设计、分析并实现新型高效并行算法。通过并行系统建模和应用程序建模的手段，分析并行系统与应用特性之间的关联关系，建立定量化性能模型，更好的指导并行算法的设计、实现和优化。本项目的研究成果将为大规模图中具有实时性要求的最短路径问题求解相关应用提供有效的支持。

Computing shortest paths in graphs is one of the most fundamental and well-studied problems in computer science. There are classical applications for this problem including logistics planning, finding routes in road and public transportation networks, social networks and so on. These applications raise new requirements as the rising of technical development. These new requirements motivate the problem from the following three aspects: (1) large scale graph data processing, (2) dynamical graph data, (3) real-time computing. This proposal will focus on real-time computing of shortest path problem on parallel computing platform(including multi-core with shared memory and cluster with distributed memory). We will design, analyze and implement new high efficient parallel algorithms. By modelling of parallel systems and application program, we will build quantitative performance model based on parallel system and application, analyze the relationship between parallel system and application characters. The performance model will be beneficial to the design, implementation and optimization of related parallel algorithms. Our research output can be applied usefully in practical applications related to the real-time computing of shortest path problem in large-scale graph.