文档介绍：基于最少换乘路径选择算法的改进摘要:最短路径是图论研究中一个最基本的算法问题,也是公交出行路线选择系统中的关键技术之一。通过分析研究目前比较流行的最短路径算法,根据人们选择出行路线的心理,提出以最少换乘为第一目标,最短路径为第二目标的思想,并以其作为基准点,对传统的广度优先搜索算法中存在的问题做出适当的改进。关键词:最短路径;广度优先搜索算法;最少换乘中图分类号:TP301文献标识码:A文章编号:1009-3044(2010)01-168-03 ImprovementsforOptimalPathSelectionAlgorithmwithMinimumTransferTimes JINGLi-rong,MAShang-cai,SHENLiang (InformationManagement,ShanxiUniversityofFinance&Economics,Taiyuan030006,China) Abstract:TheshortestpathproblemisaclassicalgorithmissueinGraphTheorystudy,,byanalyzingtheshortestpathalgorithmswhichisanideaprevailscurrentlyandconsideringpeople'spsychologywhenchoosingtravelroutes,,appropriateimprovementsaremadetothetraditionalBreadthFirstSearchalgorithm. Keywords:ShortestPath;BreadthFirstSearchAlgorithm;MinimumTransferTimes 城市道路交通网是城市的重要基础设施,它的运行直接影响着城市的规划、建设和管理。面对未来的城市,道路有效地运行,无疑是城市发展的一个重要方面。目前,解决交通拥挤的直接办法是提高路网的通行能力,增加公共交通运输能力提倡人们选择公共交通出行。但正因为路线的众多,给人们出行选择路线带来了一定的困扰。在综合考虑了时间,费用,距离的基础上,人们倾向于选择能花最少的时间,付最小的代价的路线作为出行路线。目前,已经有许多的研究者在公交最优路径选择问题中做出了相关研究。王建林提出一种基于换乘次数最少的城市公交网络最优路径算法,文中充分考虑了乘客乘车时的心理因素,并指出换乘次数最少是乘客出行时考虑的首要因素[1];胡霍真等人将最短路径算法应用到公交车网络中,并通过实验验证该算法取了较好的查询结果[2];李洪波等人提出了一种动态优化的Floyd最短路径算法,提高了算法的运行效率[3]。本文第二节简要介绍了几种比较著名的最短路径算法,并分析了其算法中所存在的问题。第三节中具体的描述了传统的广度优先搜索算法以及对公交车路线网的抽象。