带正权的无向连通图中最短路问题研究

摘要：

针对带正权的无向连通图中最短路问题,文本建立无向图最短路模型,包含边权数确定和随机两种情况,以最短路特性、逐步淘汰原则、择优原则和动态规划的基本原理为基础,提出模型的优化算法——集合法,分析了算法的正确性,并在边权数随机时对问题进行概率分析,实现了该模型的最优化.理论分析和算例表明,该模型及其优化算法适用于求解规模适中的最短路问题,有助于运筹学和图论理论的发展.

关键词： 运筹学 无向连通图 最短路模型 集合法 最优化

作者: 张薇 张立辉 乞建勋 李星梅 苏志雄

作者单位: 华北电力大学工商管理学院,北京 102206

会议类型: 国内会议

会议名称: 中国运筹学会第九届学术交流会

会议地点: 南京

会议语种:中文

页码: 278-287

在线出版日期: 2008-10-18（万方平台首次上网日期，不代表论文的发表时间）