采用广度优先搜索实现城市地铁路径规划  

作　　者：杨勇 

机构地区：[1]长江大学物理与光电工程学院,湖北荆州434032

出　　处：《电脑编程技巧与维护》2024年第12期24-26,共3页Computer Programming Skills & Maintenance

摘　　要：现代城市地铁线路日趋复杂,乘客出行往往面临选择最优换乘路线的问题。图论求解最短路径一般采用Dijkstra算法,该算法中两点间路径权值为固定值,由于线路换乘等时间因素的影响,站点间权值发生动态变化,所以运用Dijkstra算法往往不能获得正确结果。采用广度优先搜索(BFS)方法,把对目标站点的查找转换为线路的查找,通过限定换乘次数等约束条件对搜索树进行剪枝处理,再按时间优先和费用优先两种筛选模式从搜索结果集中选出最优路径,实现了高效、准确查找最优换乘路线的目标。

关 键 词：广度优先搜索 广度优先搜索 路径规划 DIJKSTRA算法 

分 类 号：U231[交通运输工程—道路与铁道工程]