计算机科学
最短路径问题
图形
组合数学
最短路径快速算法
K最短路径路由
路径(计算)
距离
最长路径问题
理论计算机科学
作者
Jiaming Yin,Weixiong Rao,Chenxi Zhang
出处
期刊:Mobile Data Management
日期:2021-06-15
卷期号:: 201-208
标识
DOI:10.1109/mdm52706.2021.00040
摘要
The shortest path problem (SPP) in graph theory has wide applications in daily travels, transportation and network routing. Existing works do not work well on large dynamic graphs and suffer from either low scalability or gealization issue. To overcome these issues, in this paper, we propose an efficient and effective learning framework, namely SPP-GS, to solve the SPP problem on large dynamic graph. The key components of SPP- GS include the techniques to decompose a large SPP instance into multiple small instance and the developed GCN-DQN model to solve small SPP instances. The evaluation result on 7 real road network graphs indicates that our approach SPP-GS performs well on large dynamic graphs by rather high quality and reasonable running time.
科研通智能强力驱动
Strongly Powered by AbleSci AI