改进的最短路径算法在多点路由上的应用

摘要：

Dijkstra算法是目前公认的较好的最短路径算法.由于多点路由问题最终归结为最短路径问题,因此将算法改进后应用于多点路由问题.提出的改进主要有以下3点:(1)改变选路策略,基于蚁群算法实现Dijkstra算法的选路操作,使选路更加灵活.(2)结合网络模型的特点,减少了对两顶点之间最短路径以外的大量顶点的计算,提高了算法的速度.(3)考虑到网络路由问题中的阻塞问题,对阻塞顶点进行标识,防止算法选择无用顶点.模拟实验结果表明改进算法较之Dijkstra算法在运算速度上有明显提高.

关键词：Dijkstra算法、蚁群算法、多点路由问题、选路策略、并行策略

所属期刊栏目：36

分类号：TP301.6(计算技术、计算机技术)

资助基金：高等学校博士学科点专项科研基金20030183060;吉林省教育厅科研项目2007248,2007251,2008411

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

页数：共4页

页码：205-207,233