基于分层图的最短路径选择问题研究  

Research on shortest path selection problem based on layered graph

作　　者：王钧盛 雷欣祺 房慧宇 孔扬涛 Wang Junsheng;Lei Xinqi;Fang Huiyu;Kong Yangtao(College of Computer and Electronic Information,Guangxi University,Nanning 530004,China)

机构地区：[1]广西大学计算机与电子信息学院,广西南宁530004

出　　处：《无线互联科技》2023年第23期136-139,共4页Wireless Internet Technology

摘　　要：路径选择问题是图论中的经典问题之一,为解决在特定约束条件下路径选择问题最短路的求取,文章采用了分层图的思想来对路径选择问题进行建模,将原图拓展为多个连接情况相同的图层,提出了一种基于分层图的最短路算法,并分别从算法思想、算法执行过程、时间复杂度等方面与传统求解方法进行比较。实验结果表明分层图最短路算法具有较低的时间复杂度与较好的性能。Path selection is a classic problem in graph theory.To solve the shortest path problem under certain constraint conditions,this paper uses the idea of layered graph to model the route selection problem.The original graph is extended to multiple graph layers with the same connection situation.A shortest path algorithm based on layered graph is proposed.The algorithm is compared with traditional methods from aspects such as algorithm ideas,execution process and time complexity.The experimental results show that the layered graph shortest path algorithm has lower time complexity and better performance.

关 键 词：最短路径 分层图 DIJKSTRA算法 优先队列 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]