| 改进的最短路径算法在多点路由上的应用 |
| |
| 引用本文： | 张毅,张猛,梁艳春. 改进的最短路径算法在多点路由上的应用[J]. 计算机科学, 2009, 36(8): 205-207 |
| |
| 作者姓名： | 张毅 张猛 梁艳春 |
| |
| 作者单位： | 1. 吉林大学计算机科学与技术学院国家教育部符号计算与知识工程重点实验室,长春,130012;吉林工商学院计算机系,长春,130062
2. 吉林大学计算机科学与技术学院国家教育部符号计算与知识工程重点实验室,长春,130012 |
| |
| 基金项目： | 高等学校博士学科点专项科研基金，吉林省教育厅科研项目 |
| |
| 摘 要： | Dijkstra算法是目前公认的较好的最短路径算法.由于多点路由问题最终归结为最短路径问题,因此将算法改进后应用于多点路由问题.提出的改进主要有以下3点:(1)改变选路策略,基于蚁群算法实现Dijkstra算法的选路操作,使选路更加灵活.(2)结合网络模型的特点,减少了对两顶点之间最短路径以外的大量顶点的计算,提高了算法的速度.(3)考虑到网络路由问题中的阻塞问题,对阻塞顶点进行标识,防止算法选择无用顶点.模拟实验结果表明改进算法较之Dijkstra算法在运算速度上有明显提高.
|
| 关 键 词： | Dijkstra算法 蚁群算法 多点路由问题 选路策略 并行策略 |
| 收稿时间： | 2008-09-28 |
| 修稿时间： | 2009-04-03 |
Application of an Improved Dijkstra Algorithm in Multicast Routing Problem |
| |
| ZHANG Yi,ZHANG Meng,LIANG Yan-chun. Application of an Improved Dijkstra Algorithm in Multicast Routing Problem[J]. Computer Science, 2009, 36(8): 205-207 |
| |
| Authors: | ZHANG Yi ZHANG Meng LIANG Yan-chun |
| |
| Affiliation: | Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education;College of Computer Science and Technology;Jilin University;Changchun 130012;China;Department of Computer Science;Jilin Business and Technology College;Changchun 130062;China |
| |
| Abstract: | Three improvements on Dijkstra algorithm were presented.The improvements were given as follows:(1)A novel optimized base on ACO implementing approach is designed to reduce the processing costs involved with routing of ants in the conventional Dijkstra algorithm.(2) Based on the model of network routing,in order to reduce the counting of other points,the set of candidates is limited to the nearest c points.(3)Marking the flags on the blocked points in order to prevent selecting these points.By this way simul... |
| |
| Keywords: | Dijkstra algorithm ACO Traveling salesman problem Parallel strategy Route strategy |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
