基于SPFA算法的公交线路优化模型  

作　　者：郭甲[1] 乔冠东[2] 李丹[2] 

机构地区：[1]河南师范大学计算机与信息技术学院,河南新乡453007 [2]中南大学土木建筑学院,湖南长沙410075

出　　处：《中国科技博览》2008年第19期52-53,共2页China Science and Technology Review

摘　　要：综合考虑换乘次数、乘车费用和乘车时间三方面因素，建立公交线路的组合优化模型。从图论的角度将问题转化为在赋权有向图中寻求最短路径，通过改进的SPFA算法求解模型。改进算法用数组储存站点的信息，队列储存待优化点，然后采用动态优化逼近的方法进行搜索，时间复杂度为，运行时间短，稳定性好，并可以得到全部的最优路线。

关 键 词：组合优化 赋权有向图 改进的SPFA算法 时间复杂性 

分 类 号：O224[理学—运筹学与控制论] U491.17[理学—数学]